Severe immune suppression is frequent in late-stage tumor patients and promotes tumor immune evasion and subsequent tumor progression. Regulatory T cells (Treg) are major suppressors of anti-tumor immune responses. Therefore, targeting of Treg has become a key goal of anti-tumor therapy. Several preclinical and clinical observations suggest that Treg can be depleted by cyclophosphamide. Over a period of 3 months, we investigated the effect of metronomic low-dose cyclophosphamide on Treg numbers, suppressive capacity and proliferation on endogenous anti-tumor T-cell responses and on their correlation to clinical outcome in 12 patients with treatment-refractory metastasized breast cancer who received single-agent 50 mg cyclophosphamide p.o. daily. Cyclophosphamide treatment initially caused a significant reduction in circulating Treg by more than 40% (P = 0.002). However, Treg numbers completely recovered during the treatment due to increased proliferative activity and maintained their suppressive capacity. Treg depletion coincided with a strong increase in breast tumor-reactive T cells (P = 0.03) that remained at high levels during the whole period. Numbers of tumor-reactive T cells but not of Treg correlated with disease stabilization (P = 0.03) and overall survival (P = 0.027). We conclude that metronomic low-dose cyclophosphamide only transiently reduces Treg but induces stable tumor-specific T-cell responses, which correlate with improved clinical outcome in advanced-stage breast cancer patients.