CD4+CD25hiCTLA4+FoxP3+ regulatory T cells (Treg) have been shown to maintain immune tolerance against self antigens and increased circulating frequencies have been reported in various types of cancers. Circulating invariant natural killer T-cells (iNKT) are reduced in cancer patients and low iNKT frequency is related to poor prognosis. It is not yet clear whether high Treg numbers and low iNKT cell numbers pose an increased risk for the progression of premalignant lesions or whether Treg and iNKT cell numbers are influenced by dysplasia. We therefore studied prospectively the relation between iNKT cell and Treg frequencies and the natural course of human papillomavirus type 16 (HPV16) induced pre-malignant cervical dysplasia in 82 patients who participated in a nonintervention cohort study of women with abnormal cytology. Treg frequencies were significantly increased in women who had persistent HPV16 infection. Within the HPV16 persistence group there was no difference in Treg frequencies among patients who developed a CIN3 lesion and patients who did not progress to CIN3. Furthermore, Treg frequencies were increased in patients who had detectable HPV16 E7 specific IL-2 producing T-helper cells, which suggests a causal role of HPV infection in Treg development in parallel with HPV16 specific T helper cells. No evidence was found for a role for iNKT cells in persistence of HPV16 and progression of HPV16 induced CIN lesions. However, HPV-persistence-associated Tregs may explain the inefficacy of concomitant persistence associated immunity and may contribute to subsequent progression to neoplasia.