Immune cells comprise a substantial proportion of the tumor mass in human nonsmall cell lung cancers (NSCLC), but the precise composition and significance of this infiltration are unclear. In this study, we examined immune complexity of human NSCLC as well as NSCLC developing in CC10-TAg transgenic mice, and revealed that CD4(+) T lymphocytes represent the dominant population of CD45(+) immune cells, and, relative to normal lung tissue, CD4(+)Foxp3(+) regulatory T cells (Tregs) were significantly increased as a proportion of total CD4(+) cells. To assess the functional significance of increased Tregs, we evaluated CD8(+) T cell-deficient/CC10-TAg mice and revealed that CD8(+) T cells significantly controlled tumor growth with antitumor activity that was partially repressed by Tregs. However, whereas treatment with anti-CD25-depleting mAb as monotherapy preferentially depleted Tregs and improved CD8(+) T cell-mediated control of tumor progression during early tumor development, similar monotherapy was ineffective at later stages. Because mice bearing early NSCLC treated with anti-CD25 mAb exhibited increased tumor cell death associated with infiltration by CD8(+) T cells expressing elevated levels of granzyme A, granzyme B, perforin, and IFN-γ, we therefore evaluated carboplatin combination therapy resulting in a significantly extended survival beyond that observed with chemotherapy alone, indicating that Treg depletion in combination with cytotoxic therapy may be beneficial as a treatment strategy for advanced NSCLC.