A strictly aerobic, halotolerant, rod-shaped bacterium, designated strain TG408, was isolated from a laboratory culture of the marine diatom Skeletonema costatum (CCAP 1077/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 Gammaproteobacteria. 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 for 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 C16:0, C16:1¿7c and C18:1¿7c. DNA G+C content for the isolate was 64.3 ± 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.