Mine tailings in semiarid regions are highly susceptible to erosion and are sources of dust pollution and potential avenues of human exposure to toxic metals. One constraint to revegetation of tailings by phytostabilization is the absence of microbial communities critical for biogeochemical cycling of plant nutrients. The objective of this study was to evaluate specific genes as in situ indicators of biological soil response during phytoremediation. The abundance and activity of 16S rRNA, nifH, and amoA were monitored during a nine month phytostabilization study using buffalo grass and quailbush grown in compost-amended, metalliferous tailings. The compost amendment provided a greater than 5-log increase in bacterial abundance, and survival of this compost-inoculum was more stable in planted treatments. Despite increased abundance, the activity of the introduced community was low, and significant increases were not detected until six and nine months in quailbush, and unplanted compost and buffalo grass treatments, respectively. In addition, increased abundances of nitrogen-fixation (nifH) and ammonia-oxidizing (amoA) genes were observed in rhizospheres of buffalo grass and quailbush, respectively. Thus, plant establishment facilitated the short term stabilization of introduced bacterial biomass and supported the growth of two key nitrogen-cycling populations in compost-amended tailings.