Arhodomonas sp. strain Seminole was isolated from a crude oil-impacted brine soil and shown to degrade benzene, toluene, phenol, 4-hydroxybenzoic acid (4-HBA), protocatechuic acid (PCA), and phenylacetic acid (PAA) as the sole sources of carbon at high salinity. Seminole is a member of the genus Arhodomonas in the class Gammaproteobacteria, sharing 96% 16S rRNA gene sequence similarity with Arhodomonas aquaeolei HA-1. Analysis of the genome predicted a number of catabolic genes for the metabolism of benzene, toluene, 4-HBA, and PAA. The predicted pathways were corroborated by identification of enzymes present in the cytosolic proteomes of cells grown on aromatic compounds using liquid chromatography-mass spectrometry. Genome analysis predicted a cluster of 19 genes necessary for the breakdown of benzene or toluene to acetyl coenzyme A (acetyl-CoA) and pyruvate. Of these, 12 enzymes were identified in the proteome of toluene-grown cells compared to lactate-grown cells. Genomic analysis predicted 11 genes required for 4-HBA degradation to form the tricarboxylic acid (TCA) cycle intermediates. Of these, proteomic analysis of 4-HBA-grown cells identified 6 key enzymes involved in the 4-HBA degradation pathway. Similarly, 15 genes needed for the degradation of PAA to the TCA cycle intermediates were predicted. Of these, 9 enzymes of the PAA degradation pathway were identified only in PAA-grown cells and not in lactate-grown cells. Overall, we were able to reconstruct catabolic steps for the breakdown of a variety of aromatic compounds in an extreme halophile, strain Seminole. Such knowledge is important for understanding the role of Arhodomonas spp. in the natural attenuation of hydrocarbon-impacted hypersaline environments.