Polycyclic aromatic hydrocarbons (PAHs) are widely distributed and relocated in the environment as a result of the incomplete combustion of organic matter. Many PAHs and their epoxides are highly toxic, mutagenic and/or carcinogenic to microorganisms as well as to higher systems including humans. Although various physicochemical methods have been used to remove these compounds from our environment, they have many limitations. Xenobiotic-degrading microorganisms have tremendous potential for bioremediation but new modifications are required to make such microorganisms effective and efficient in removing these compounds, which were once thought to be recalcitrant. Metabolic engineering might help to improve the efficiency of degradation of toxic compounds by microorganisms. However, efficiency of naturally occurring microorganisms for field bioremediation could be significantly improved by optimizing certain factors such as bioavailability, adsorption and mass transfer. Chemotaxis could also have an important role in enhancing biodegradation of pollutants. Here, we discuss the problems of PAH pollution and PAH degradation, and relevant bioremediation efforts.