Benzene, toluene, ethylbenzene, and xylene (BTEX) compounds are of great environmental concern due to their toxicity and carcinogenicity. Bacterial removal of BTEX has proven to be highly efficient, cost-effective, and nondisruptive, provided that, efficient bacterial degraders are available. The objective of this study, therefore, is to discover aerobic bacterial degraders with their relative pathways that could be employed for the efficient removal of individual BTEX compounds. A total of 22 petroleum hydrocarbon degrading aerobic bacteria from the river water in close vicinity to a petrol refinery were isolated and identified previously. These bacteria were further screened for their potential to degrade individual BTEX compounds. Primary selection of BTEX degraders was carried out by using conventional enrichment culture technique and gas chromatography/mass spectrophotometry (GC/MS) analyses. Out of the 22 isolates, five were found to degrade BTEX efficiently and further characterized through PCR analyses for their initial attack and cleavage genes as well as GC/MS analyses of the intermediate metabolites to decipher the degradation pathways used. The study elucidates new efficient bacterial strains of Acinetobacter calcoaceticus Fe10, Serratia nematodiphila Mn11, Raoultella planticola Ag11, Pseudomonas koreensis Hg11, and Micrococcus luteus Sr11 with their relative pathways for aerobic removal of the individual BTEX compounds.