Downregulation of MHC class I expression on the cell surface is a common mechanism by which tumour cells, including cervical carcinoma, can escape the T cell-mediated anti-tumour immunity. This downregulation represents an obstacle for the efficacy of anti-tumour vaccines. In this study, we investigated the efficacy of prophylactic peptide and peptide-pulsed dendritic cell-based vaccines in a murine model of experimental MHC class I-deficient tumours (TC-1/A9), expressing E6/E7 oncogenes derived from HPV16, and compared the efficacy of particular vaccination settings to anti-tumour protection against parental MHC class I-positive TC-1 tumours. Peptide vaccine based on the 'short' peptide E749-57 harbouring solely the CTL epitope and co-administered to the C57BL/6 mice with CpG oligodeoxynucleotide (CpG ODN) 1826 was effective against MHC class I-positive but not -deficient tumours, while the 'longer' peptide E744-62 (peptide 8Q, harbouring CTL and Th epitopes)-based vaccines were also effective against MHC class I-deficient tumours. We have compared the adjuvant efficacies of two CpG ODN, CpG ODN 1826 and CpG ODN 1585. The 8Q peptide immunisation combined with CpG ODN 1585 inhibited growth of the TC-1/A9 tumours more effectively as compared to CpG ODN 1826. Further, we investigated the efficacy of cellular vaccines based on ex vivo cultured dendritic cells pulsed with either E749-57 or E744-62 peptides and matured with CpG ODN 1826. Unlike in the peptide immunisation setting, treatment with dendritic cells pulsed with a 'short' peptide resulted in the tumour growth inhibition, albeit weaker as compared to the immunisation with the longer peptide. Our data demonstrate that peptide and dendritic cell-based vaccines can be designed to elicit protective immunity against MHC class I-deficient tumours.