Bacterial degradation of crude oil is a promising strategy for reducing the concentration of hydrocarbons in contaminated environments. In the first part of this study, we report the enrichment of two bacterial consortia from deep sediments of the Gulf of Mexico with crude oil as the sole carbon and energy source. We conducted a comparative analysis of the bacterial community in the original sediment, assessing its diversity, and compared it to the enrichment observed after exposure to crude oil in defined cultures. The consortium exhibiting the highest hydrocarbon degradation was predominantly enriched with Rhodococcus (75%). Bacterial community analysis revealed the presence of other hydrocarbonoclastic members in both consortia. In the second part, we report the isolation of the strain Rhodococcus sp. GOMB7 with crude oil as a unique carbon source under microaerobic conditions and its characterization. This strain demonstrated the ability to degrade long-chain alkanes, including eicosane, tetracosane, and octacosane. We named this new strain Rhodococcus qingshengii GOMB7. Genome analysis revealed the presence of several genes related to aromatic compound degradation, such as benA, benB, benC, catA, catB, and catC; and five alkB genes related to alkane degradation. Although members of the genus Rhodococcus are well known for their great metabolic versatility, including the aerobic degradation of recalcitrant organic compounds such as petroleum hydrocarbons, this is the first report of a novel strain of Rhodococcus capable of degrading long-chain alkanes under microaerobic conditions. The potential of R. qingshengii GOMB7 for applications in bioreactors or controlled systems with low oxygen levels offers an energy-efficient approach for treating crude oil-contaminated water and sediments.