A strictly aerobic, halotolerant, rod-shaped bacterium, designated strain TG408, was isolated from a laboratory culture of the marine diatom Skeletonema costatum (CCAP1077/1C) by enrichment with polycyclic aromatic hydrocarbons (PAHs) as the sole carbon source. 16S rRNA gene sequence analysis placed this organism within the order Xanthomonadales of the class Gammaproteobacteria. Its closest relatives included representatives of the Hydrocarboniphaga-Nevskia-Sinobacter clade (<92% sequence similarity) in the family Sinobacteraceae. The strain exhibited a narrow nutritional spectrum, preferring to utilize aliphatic and aromatic hydrocarbon compounds and small organic acids. Notably, it displayed versatility in degrading two- and three-ring PAHs. Moreover, catechol 2,3-dioxygenase activity was detected in lysates, indicating that this strain utilizes the meta-cleavage pathway for aromatic compound degradation. Cells produced surface blebs and contained a single polar flagellum. The predominant isoprenoid quinone of strain TG408 was Q-8, and the dominant fatty acids were C(16:0), C(16:1) ω7c, and C(18:1) ω7c. The G+C content of the isolate's DNA was 64.3 mol% ± 0.34 mol%. On the basis of distinct phenotypic and genotypic characteristics, strain TG408 represents a novel genus and species in the class Gammaproteobacteria for which the name Polycyclovorans algicola gen. nov., sp. nov., is proposed. Quantitative PCR primers targeting the 16S rRNA gene of this strain were developed and used to show that this organism is found associated with other species of marine phytoplankton. Phytoplankton may be a natural biotope in the ocean where new species of hydrocarbon-degrading bacteria await discovery and which contribute significantly to natural remediation processes.