Increasing evidence supports the concept of a unique population of cells within a tumour with stem-like characteristics. These cancer-stem cells (CSCs) are thought to be responsible for tumour organization, maintenance, progression and recurrence. In this study we outline a new characteristic of CSCs, one in which the CSC can subvert the host immune response. We pose that this characteristic is essential for the establishment of a tumour in an immunocompetent host and may represent a mechanism in which tumours gain resistance to acquired anti-cancer immune responses and immune based therapies. To test this we vaccinated mice against the HPV E7 antigen and challenged them with HPV E6/7 expressing cancer cells (TC-1) enriched for CSCs. We found that mice vaccinated and challenged with non-CSC enriched populations exhibited a significant prolongation of survival compared to unvaccinated animals (P=0.007). In contrast, vaccinated mice challenged with the CSC enriched populations showed no improvements in survival when compared to non-vaccinated animals (P>0.05), indicating that the CSCs may be intrinsically resistant to immune-mediated control. To confirm this, we conducted ex-vivo cytolytic assays with CD8+ T cells isolated from vaccinated mice. We showed that significantly fewer CSCs were capable of being lysed by CD8+ T cells compared to non-CSCs at all effector to target cell (E:T) ratios, P≤0.004. Similarly, CD8+ T cells cultured with CSCs demonstrated significantly less IFN-γ secretion than CD8+ T cells co-cultured with non-CSCs, P≤0.001. Using flow-cytometry we show that CSCs have down-regulated surface expression of MHC-I and that we could increase MHC-I expression on CSCs by treating the cells with IFN-γ. The increase of MHC-I on the surface of CSCs improved sensitivity to vaccine induced CD8+ T cells and lead to the inhibition of tumour take/initiation in immunocompetent mice.