The concentration of CO2 in the Earth’s atmosphere has increased over the last century. Although this increase is unlikely to have direct effects on soil microbial communities, increased atmospheric CO2 may impact soil ecosystems indirectly through plant responses. This study tested the hypothesis that exposure of plants to elevated CO2 would impact soil microorganisms responsible for key nitrogen cycling processes, specifically denitrification and nitrification. We grew trembling aspen (Populus tremuloides) trees in outdoor chambers under ambient (360 ppm) or elevated (720 ppm) levels of CO2 for 5 years and analyzed the microbial communities in the soils below the trees using quantitative polymerase chain reaction and clone library sequencing targeting the nitrite reductase (nirK) and ammonia monooxygenase (amoA) genes. We observed a more than twofold increase in copy numbers of nirK and a decrease in nirK diversity with CO2 enrichment, with an increased predominance of Bradyrhizobia-like nirK sequences. We suggest that this dramatic increase in nirK-containing bacteria may have contributed to the significant loss of soil N in the CO2-treated chambers. Elevated CO2 also resulted in a significant decrease in copy numbers of bacterial amoA, but no change in archaeal amoA copy numbers. The decrease in abundance of bacterial amoA was likely a result of the loss of soil N in the CO2-treated chambers, while the lack of response for archaeal amoA supports the hypothesis that physiological differences in these two groups of ammonia oxidizers may enable them to occupy distinct ecological niches and respond differently to environmental change.