Immunotherapy with DCs as antigen-presenting vehicles have already improved patients' outcome against a variety of tumors. Moreover, MSCs were recently used to develop anti-cancer therapeutic or anti-microbial prophylactic vaccines. The current study evaluated immune responses and anti-tumor effects generated by DCs and MSCs derived from mouse bone marrow which were modified with small heat shock proteins 27 and 20 (sHsp27 and sHsp20) and also E7 oncoprotein in tumor mouse model. Two vaccination strategies were utilized including homologous DC or MSC prime/ DC or MSC boost, and heterologous MSC or DC prime/ protein boost vaccinations. Our data revealed that DCs pulsed with E7+Hsp27 and/or E7+Hsp20 in homologous and heterologous prime/ boost vaccinations could stimulate high levels of IgG2a, IgG2b, IFN-γ and IL-10 directed toward Th1 responses. Moreover, these regimens induced an increased level of Granzyme B, and displayed complete protection more than 60 days after treatment. On the other hand, MSCs transfected with E7+Hsp27 DNA in homologous and heterologous prime/ boost vaccinations could significantly enhance the E7-specific T-cell responses and suppress tumor growth in mice. However, MSCs transfected with E7+Hsp20 DNA did not induce a complete protection against TC-1 tumor compared to DCs pulsed with E7+Hsp20 protein complexes. These results indicated that DC- and MSC-based vaccinations with specific modalities will be a useful approach for immunotherapy and protection against HPV-associated cancers.