Seven xylene-utilizing bacterial strains were isolated from seawater collected off the coast of Japan. Analysis of 16S rRNA gene sequences indicated that six isolates were most closely related to the marine bacterial genera Alteromonas, Marinobacter or Aestuariibacter. The sequence of the remaining strain, KU68FT, showed low similarity to the 16S rRNA gene sequences of known bacteria with validly published names, the most similar species being Maricurvus nonylphenolicus strain KU41ET (92.6% identity). On the basis of physiological, chemotaxonomic and phylogenetic data, strain KU68FT is suggested to represent a novel species of a new genus in the family Cellvibrionaceae of the order Cellvibrionales within the Gammaproteobacteria, for which the name Halioxenophilus aromaticivorans gen. nov., sp. nov. is proposed. The type strain of Halioxenophilus aromaticivorans is KU68FT (=JCM 19134T = KCTC 32387T). PCR and sequence analysis revealed that strain KU68FT possesses an entire set of genes encoding the enzymes for the upper xylene methyl-monooxygenase pathway, xylCMABN, resembling the gene set of the terrestrial Pseudomonas putida strain mt-2.