Heterologous prime-boost vaccination employing DNA-vaccinia virus (VACV) modality using the Leishmania homologue of receptors for activated C kinase (LACK) (p36) antigen has been shown to elicit protective immunity against both murine cutaneous and visceral leishmaniasis. However, DNA priming is known to have limited efficacy; therefore in the current study the effect of NKT cell activation using alpha-galactosyl-ceramide (alphaGalCer) during intradermal DNAp36 priming was examined. Vaccinated mice receiving alphaGalCer + DNAp36 followed by a boost with VVp36 appeared to be resolving their lesions and had at ten- to 20-fold higher reductions in parasite burdens. NKT cell activation during alphaGalCer + DNAp36 priming resulted in higher numbers of antigen-reactive effector CD4(+) and CD8(+) T cells producing granzyme and IFN-gamma, with lower levels of IL-10. Although immunodepletion studies indicate that both CD4 and CD8 T cells provide protection in the vaccinated mice, the contribution of CD4(+) T cells was significantly increased in mice primed with DNAp36 together with alphaGalCer. Notably 5 months after boosting, mice vaccinated with DNAp36 + alphaGalCer continued to show sustained and heightened T cell immune responses. Thus, heterologous prime-boost vaccination using alphaGalCer during priming is highly protective against murine cutaneous leishmaniasis, resulting in the heightened activation and development of CD4 and CD8 T cells (effector and memory T cells).