Marine hydrocarbon-degrading bacteria play an important role in natural petroleum biodegradation processes and were initially associated with man-made oil spills or natural seeps. There is no full clarity though on what, in the absence of petroleum, their natural niches are. Few studies pointed at some marine microalgae that produce oleophilic compounds (alkanes, long-chain fatty acids, and alcohols) as potential natural hosts of these bacteria. We established Dansk crude oil-based enrichment cultures with photobioreactor-grown marine microalgae cultures Pavlova lutheri and Nannochloropsis oculata and analyzed the microbial succession using cultivation and SSU (16S) rRNA amplicon sequencing. We found that petroleum enforced a strong selection for members of Alpha- and Gamma-proteobacteria in both enrichment cultures with the prevalence of Alcanivorax and Marinobacter spp., well-known hydrocarbonoclastic bacteria. In total, 48 non-redundant bacterial strains were isolated and identified to represent genera Alcanivorax, Marinobacter, Thalassospira, Hyphomonas, Halomonas, Marinovum, Roseovarius, and Oleibacter, which were abundant in sequencing reads in both crude oil enrichments. Our assessment of public databases demonstrated some overlaps of geographical sites of isolation of Nannochloropsis and Pavlova with places of molecular detection and isolation of Alcanivorax and Marinobacter spp. Our study suggests that these globally important hydrocarbon-degrading bacteria are associated with P. lutheri and N. oculata.