Petroleum is the most common global fossil fuel. It is a complex multi-component system mainly composed of various hydrocarbons such as alkanes, cycloalkanes, mono-, bi- and polyaromatic compounds, resins and asphaltenes. In spite of humanity’s need for petroleum, it negatively affects the environment due to its toxicity. The ecological problem is especially serious at petroleum mining sites or during petroleum transportation. Since it is not possible to replace petroleum with less toxic fuel, ways to reduce the toxic impact of petroleum hydrocarbons on the environment need to be developed. This review addresses bioremediation, a biological approach to petroleum degradation, which is mainly performed by microbes. The pathways of degradation of alkanes, alkenes and aromatic hydrocarbons are presented in detail. The effects of temperature, aeration and the presence of biogenic elements on microbial degradation of petroleum are discussed. Plant−microbe interactions involved with the bioremediation of petroleum-polluted soils are specifically addressed. The data presented in this review point to the great potential of bioremediation practices for cleaning soils of petroleum.