This study assessed the ability of phosphorus (P) fertilizer to remediate the rhizosphere of three wild plant species (Banksia seminuda, a tree; Chloris truncata, a grass; and Hakea prostrata, a shrub) growing in a soil contaminated with total (aliphatic) petroleum hydrocarbon (TPH). Plant growth, photosynthesis (via chlorophyll fluorescence), soil microbial activity, alkane hydroxylase AlkB (aliphatic hydrocarbon-degrading) gene abundance, and TPH removal were evaluated 120 days after planting. Overall, although TPH served as an additional carbon source for soil microorganisms, the presence of TPH in soil resulted in decreased plant growth and photosynthesis. However, growth, photosynthesis, microbial activities, and AlkB gene abundance were enhanced by the application of P fertilizer, thereby increasing TPH removal rates, although the extent and optimum P dosage varied among the plant species. The highest TPH removal (64.66%) was observed in soil planted with the Poaceae species, C. truncata, and amended with 100 mg P kg−1 soil, while H. prostrata showed higher TPH removal compared to the plant belonging to the same Proteaceae family, B. seminuda. The presence of plants resulted in higher AlkB gene abundance and TPH removal relative to the unplanted control. The removal of TPH was associated directly with AlkB gene abundance (R2 > 0.9, p < 0.001), which was affected by plant identity and P levels. The results indicated that an integrated approach involving wild plant species and optimum P amendment, which was determined through experimentation using different plant species, was an efficient way to remediate soil contaminated with TPH.