Claudin-low breast cancer is an aggressive subtype that confers poor prognosis and is found largely within the clinical triple-negative group of breast cancer patients. Here, we have shown that intrinsic and immune cell gene signatures distinguish the claudin-low subtype clinically as well as in mouse models of other breast cancer subtypes. Despite adaptive immune cell infiltration in claudin-low tumors, treatment with immune checkpoint inhibitory antibodies against cytotoxic T lymphocyte-associated protein 4 (CTLA-4) and programmed death receptor 1 (PD-1) were ineffective in controlling tumor growth. CD4+FoxP3+ Tregs represented a large proportion of the tumor-infiltrating lymphocytes (TILs) in claudin-low tumors, and Tregs isolated from tumor-bearing mice were able to suppress effector T cell responses. Tregs in the tumor microenvironment highly expressed PD-1 and were recruited partly through tumor generation of the chemokine CXCL12. Antitumor efficacy required stringent Treg depletion combined with checkpoint inhibition; delays in tumor growth were not observed using therapies that modestly diminished the number of Tregs in the tumor microenvironment. This study provides evidence that the recruitment of Tregs to the tumor microenvironment inhibits an effective antitumor immune response and highlights early Treg recruitment as a possible mechanism for the lack of response to immune checkpoint blockade antibodies in specific subtypes of cancer that are heavily infiltrated with adaptive immune cells.