Bioremediation has a long tradition in cleaning PAH-contaminated soils. Much of the early know-how is derived from remediation of mineral oil spills or spills of oily wastes. These hydrocarbons seem to be readily degradable in soils. PAH contaminations, however, seem to be rather resistant to known remediation strategies. This was mainly attributed to the low bioavailability of PAHs, the formation of bound residues, and the missing of the necessary enzymes. In the last years, knowledge about biodegradation strategies of soil microorganisms has increased considerably and new strategies such as bioaugmentation of soils with selected strains and microbial communities, or bioaugmentation with transmissible genetic elements have been developed. Consequently, bioremediation strategies for PAH-contaminated soils have to be discussed in a new light. In this review we give an overview over the current discussion in this field.