A novel indigenous bacterium, strain JM10, isolated from the oligotrophic Hei He reservoir was characterized and showed aerobic denitrification ability. JM10 was identified as Bacillus sp. by phylogenetic analysis of its 16S rRNA gene sequence. Strain JM10 displayed very high levels of activity in aerobic conditions, consuming over 94.3% NO3−-N (approximately 3.06 mg L−1) with a maximum reduction rate of 0.108 mg NO3−-N L−1 h−1. Full-factorial Box–Behnken design and response surface methodology were employed to investigate the optimal nitrate degradation conditions. The optimum conditions for nitrate degradation, at a rate of 0.140 mg L−1 h−1, were found to be an inoculum size of 16.3% v/v, initial pH of 7.6, C/N ratio of 7.4, and temperature of 27.4 °C, and the C/N ratio and temperature had the largest effect on the nitrate degradation rate. Strain JM10 was added into the water samples from Hei He reservoir and the total nitrogen and nitrate removal rates of the strain reached 66.5% and 100%, respectively. Therefore, our results demonstrate that the strain JM10 favored the bioremediation of the oligotrophic reservoir.