A large number of aromatic compounds and organic nitriles, the two groups of compounds covered in this review, are intermediates, products, by-products or waste products of the chemical and pharmaceutical industries, agriculture and the processing of fossil fuels. The majority of these synthetic substances (xenobiotics) are toxic and their release and accumulation in the environment pose a serious threat to living organisms. Bioremediation using various bacterial strains of the genus Rhodococcus has proved to be a promising option for the clean-up of polluted sites. The large genomes of rhodococci, their redundant and versatile catabolic pathways, their ability to uptake and metabolize hydrophobic compounds, to form biofilms, to persist in adverse conditions and the availability of recently developed tools for genetic engineering in rhodococci make them suitable industrial microorganisms for biotransformations and the biodegradation of many organic compounds. The peripheral and central catabolic pathways in rhodococci are characterized for each type of aromatics (hydrocarbons, phenols, halogenated, nitroaromatic, and heterocyclic compounds) in this review. Pathways involved in the hydrolysis of nitrile pollutants (aliphatic nitriles, benzonitrile analogues) and the corresponding enzymes (nitrilase, nitrile hydratase) are described in detail. Examples of regulatory mechanisms for the expression of the catabolic genes are given. The strains that efficiently degrade the compounds in question are highlighted and examples of their use in biodegradation processes are presented.