Pseudoxanthomonas spadix BD-a59, isolated from gasoline-contaminated soil, has the ability to degrade all six BTEX (benzene, toluene, ethylbenzene, and o-, m-, and p-xylene) compounds. The genomic features of strain BD-a59 were analyzed bioinformatically and compared with those of another fully sequenced Pseudoxanthomonas strain, P. suwonensis 11-1, which was isolated from cotton waste compost. The genome of strain BD-a59 differed from that of strain 11-1 in many characteristics, including the number of rRNA operons, dioxygenases, monooxygenases, genomic islands (GIs), and heavy metal resistance genes. A high abundance of phage integrases and GIs and the patterns in several other genetic measures (e.g., GC content, GC skew, Karlin signature, and clustered regularly interspaced short palindromic repeat [CRISPR] gene homology) indicated that strain BD-a59's genomic architecture may have been altered through horizontal gene transfers (HGT), phage attack, and genetic reshuffling during its evolutionary history. The genes for benzene/toluene, ethylbenzene, and xylene degradations were encoded on GI-9, -13, and -21, respectively, which suggests that they may have been acquired by HGT. We used bioinformatics to predict the biodegradation pathways of the six BTEX compounds, and these pathways were proved experimentally through the analysis of the intermediates of each BTEX compound using a gas chromatograph and mass spectrometry (GC-MS). The elevated abundances of dioxygenases, monooxygenases, and rRNA operons in strain BD-a59 (relative to strain 11-1), as well as other genomic characteristics, likely confer traits that enhance ecological fitness by enabling strain BD-a59 to degrade hydrocarbons in the soil environment.