Exploiting synergism between plants and microbes offers a potential means of remediating soils contaminated with petroleum hydrocarbons (PHCs). Salinity alters the physicochemical characteristics of soils and suppresses the growth of both plants and soil microbes, so the bioremediation of saline soils requires the use of plants and in microbes which can tolerate salinity. This review focuses on the management of PHC-contaminated saline soils, surveying what is currently known with respect to the potential of halophytes (plants adapted to saline environments) acting in concert with synergistic microbes to degrade PHCs. The priority is to identify optimal combinations of halophyte(s) and the bacteria present as endophytes and/or associated with the rhizosphere, and to determine what are the factors which most strongly affect their viability.