Protocols of immunization based on the DNA prime/vaccinia virus (VV) boost regime with recombinants expressing relevant antigens have been shown to elicit protection against a variety of pathogens in animal model systems, and various phase I clinical trials have been initiated with this vaccination approach. We have previously shown that mice immunized with a DNA vector expressing p36/LACK of Leishmania infantum followed by a booster with VVp36/LACK induced significant protection against Leishmania major infection. To further improve this protocol of immunization, here we investigated whether the cytokines interleukin-12 (IL-12) and IL-18 could enhance protection against L. major infection in BALB/c mice. We found that priming with DNA vectors expressing p36/LACK and either IL-12 or IL-18, followed by a booster with a VV recombinant expressing the same L. infantum LACK antigen, elicit a higher cellular immune response than by using the same protocol in the absence of the cytokines. The cytokine IL-12 triggered a higher number of IFN-gamma-secreting cells specific for p36 protein than IL-18. When immunized animals were challenged with promastigotes, the highest protection against L. major infection was observed in animals primed with DNAp36 + DNA IL-12 + DNA IL-18 and boosted with VVp36. This protection correlated with a Th1 type of immune response. Our findings revealed that in prime/booster protocols, co-expressing IL-12 and IL-18 during priming is an efficient approach to protect against leishmaniasis. This combined prime/booster immunization regime could have wide use in fighting against parasitic and other infectious diseases.