The simultaneous aerobic removal of a mixture of benzene, toluene, ethylbenzene, and o,m,p-xylene (BTEX); cis-dichloroethylene (cis-DCE); and trichloroethylene (TCE) from the artificially contaminated water using an indigenous bacterial isolate identified as Pseudomonas plecoglossicida immobilized on waste scrap tyres was investigated. Suspended and immobilized conditions were compared for the removal of these volatile organic compounds. For the immobilized system, toluene, benzene, and ethylbenzene were completely removed, while the highest removal efficiencies of 99.0 ± 0.1, 96.8 ± 0.3, 73.6 ± 2.5, and 61.6 ± 0.9% were obtained for o-xylene, m,p-xylene, TCE, and cis-DCE, respectively. The sorption kinetics of contaminants towards tyre surface was also evaluated, and the sorption capacity generally followed the order of toluene > benzene > m,p-xylene > o-xylene > ethylbenzene > TCE > cis-DCE. Scrap tyres showed a good capability for the simultaneous sorption and bioremoval of BTEX/cis-DCE/TCE mixture, implying a promising waste material for the removal of contaminant mixture from industrial wastewater or contaminated groundwater.