Various immune functions of different types of immune cells are strongly impaired in patients with head and neck squamous cell carcinoma (HNSCC). Regulatory T-lymphocyte cells (Tregs) have been suggested to be involved in the immunomodulation of immune responses and contribute to HNSCC progression and immune escape. 'Naturally' occurring CD4+CD25+ Tregs represent a small fraction within the different subsets of regulatory T cells, which are known to inhibit numerous immune functions of different types of immune cells. In this study, the cellular ratio of CD4+CD25 high Tregs to the entire population of CD4+ T-lymphocytes was analyzed with respect to different stages of tumor progression and disease. Our data indicate a significantly high increased abundance of CD4 +CD25highCD127low Tregs in the peripheral blood of patients with HNSCC, which in addition show modulated expression levels of various functional proteins. Surprisingly, increased Treg levels were found even in patients with no active disease several years after tumor resection, with no significant correlation to the individual tumor stage. Additionally, increased levels of chemokine CCL22, which mediates migration of Tregs to the tumor, and upregulation of the corresponding receptor protein CCR4 were observed in HNSCC. Our data strongly suggest that HNSCC leads to a permanent shift of Treg levels with hardly recognizable recovery rates.