Pollution of soil and water by crude and refined oil has been, and is still today, an important environmental problem. In crude and refined oil, alkanes are saturated hydrocarbons and represent the major fraction. Although alkanes are chemically quite inert, various alkane-degrading bacteria, isolated from soil, water, sediment, and plant, can utilize them as carbon and energy source. Alkane-degrading bacteria belong to different species depending on the type (short-, medium-, and long-chain alkanes) and concentration of alkanes in their habitat. These bacteria play a crucial role in the microbial degradation of oil, chlorinated hydrocarbons, fuel additives, and many other compounds. Environmental investigations reveal the abundance and ecological role of oil-degrading bacteria in environments and have led to the identification of many alkane degraders, including some that are (near)-obligate alkanotrophs. Alkane-degrading bacteria in combination with plants can remediate oil-contaminated soils more efficiently than alone. Plants and alkane-degrading bacteria can form specific interactions in which the plant supplies the bacteria with a special carbon source that stimulates the bacteria to degrade alkane hydrocarbons. In return, plants can benefit from these bacteria-possessing alkane degradation pathways and metabolic capabilities, leading to more efficient hydrocarbon degradation and reduction of phytotoxicity. A better knowledge of plant–bacteria interactions could be exploited to enhance the remediation of alkanes and other hydrocarbons from contaminated soils in conjunction with sustainable production of nonfood crops for biomass and biofuel production. This review concentrates on the distribution of alkane-degrading bacteria in the environment and their interactions with plants that enhance the remediation of oil-contaminated soil.