We evaluated the capacity of NK cells to influence expansion of CD4+ CD25+ FoxP3+ regulatory T cells (Tregs) in response to microbial Ags, using Mycobacterium tuberculosis as a model. We previously found that Tregs expand when CD4+ cells and monocytes are exposed to M. tuberculosis. Addition of NK cells that were activated by monokines (IL-12, IL-15, and IL-18) or by exposure to M. tuberculosis-stimulated monocytes reduced Treg expansion in response to M. tuberculosis. NK cell inhibition of Treg expansion was not mediated through IFN-γ. Activated NK cells lysed expanded, but not freshly isolated Tregs. Although monokines increased NK cell expression of the activating receptors NKp46, NKG2D, 2B4, CD16, and DNAM-1, only anti-NKG2D and anti-NKp46 inhibited NK cell lysis of expanded Tregs. Of five NKG2D ligands, only UL16-binding protein 1 (ULBP1) was up-regulated on M. tuberculosis-expanded Tregs, and anti-ULBP1 inhibited NK cell lysis of expanded Tregs. M. tuberculosis-stimulated monocytes activated NK cells to lyse expanded Tregs, and this was also inhibited by anti-NKG2D and anti-ULBP1, confirming the physiological relevance of this effect. Our study identifies a potential new role for NK cells in maintaining the delicate balance between the regulatory and effector arms of the immune response.