We analysed the genome of the aromatic hydrocarbon-degrading, facultatively chemolithotrophic betaproteobacterium, Polaromonas naphthalenivorans strain CJ2. Recent work has increasingly shown that Polaromonas species are prevalent in a variety of pristine oligotrophic environments, as well as polluted habitats. Besides a circular chromosome of 4.4 Mb, strain CJ2 carries eight plasmids ranging from 353 to 6.4 kb in size. Overall, the genome is predicted to encode 4929 proteins. Comparisons of DNA sequences at the individual gene, gene cluster and whole-genome scales revealed strong trends in shared heredity between strain CJ2 and other members of the Comamonadaceae and Burkholderiaceae. blastp analyses of protein coding sequences across strain CJ2's genome showed that genetic commonalities with other betaproteobacteria diminished significantly in strain CJ2's plasmids compared with the chromosome, especially for the smallest ones. Broad trends in nucleotide characteristics (GC content, GC skew, Karlin signature difference) showed at least six anomalous regions in the chromosome, indicating alteration of genome architecture via horizontal gene transfer. Detailed analysis of one of these anomalous regions (96 kb in size, containing the nag-like naphthalene catabolic operon) indicates that the fragment's insertion site was within a putative MiaB-like tRNA-modifying enzyme coding sequence. The mosaic nature of strain CJ2's genome was further emphasized by the presence of 309 mobile genetic elements scattered throughout the genome, including 131 predicted transposase genes, 178 phage-related genes, and representatives of 12 families of insertion elements. A total of three different terminal oxidase genes were found (putative cytochrome aa(3)-type oxidase, cytochrome cbb(3)-type oxidase and cytochrome bd-type quinol oxidase), suggesting adaptation by strain CJ2 to variable aerobic and microaerobic conditions. Sequence-suggested abilities of strain CJ2 to carry out nitrogen fixation and grow on the aromatic compounds, biphenyl and benzoate, were experimentally verified. These new phenotypes and genotypes set the stage for gaining additional insights into the physiology and biochemistry contributing to strain CJ2's fitness in its native habitat, contaminated sediment.