Phyto-stimulation, the use of plants to stimulate activity of microorganisms in a root zone, has been proposed as an approach to promote the degradation of petroleum hydrocarbons and thus the remediation of petroleum-polluted soils. In this study, we investigated the potential use of sewage sludge to enhance phyto-stimulating effects of maize (Zea mays L.) on the elimination of an aged petroleum contamination in a calcareous soil. In a pot experiment, maize was grown on the experimental soil for two months at three levels of sewage sludge application (0, 20, and 50 g dry matter of sludge per kg soil). The amendments increased root and shoot growth of the experimental plants approximately by a factor of two at the lower sludge treatment level and by a factor of five at the higher sludge treatment level. In a separate incubation experiment, sludge application also led to an immediate stimulation of soil respiration, which then further increased over time. The initial stimulation was three times larger at the higher than at the lower treatment level, but the rate of subsequent increase was similar in both treatments. The two sludge treatments also accelerated TPH elimination in the contaminated soil, and again the effect was approximately three times stronger at the higher than at the lower treatment level. The sludge effect on TPH elimination was much stronger than the effect of the plants. More than half of the initial contamination was reduced in combined treatment with maize and sludge application at the highest rate. The results show that sewage sludge can substantially enhance the remediation of petroleum-contaminated soil, especially when applied in conjunction with a suitable plant such as maize.