The mechanisms underlying the protective effects induced by dendritic cells (DC)-based vaccines against Leishmania major in mice are not yet completely understood. In the present study, we investigated the potential of DC loaded with a mixture of the Leishmania infantum histones in the absence (HIS-pulsed DC) or presence of CpG motifs (HIS+CpG-pulsed DC) as a candidate vaccine against cutaneous leishmaniosis. Our data showed that a single intravenous administration of HIS-pulsed DC or HIS+CpG-pulsed DC confers control to L. major infection in BALB/c mice. Interestingly, all HIS-pulsed DC vaccinated mice remained susceptible to a second challenge. We found that the efficient immunity in BALB/c mice was associated to a Th1 response and a restriction of Th2 type of response upon challenge with L. major parasites. More importantly, the anti-leishmanial immunological mechanisms of protection were dependent on the ability to induce a low frequency of Foxp3(+) regulatory T cells at the site of infection. These results document that a vaccine based on a HIS+CpG-pulsed DC formulation may be as efficient for vaccination as one based on L. major antigen (Lm)+CpG-pulsed DC. Thus, HIS+CpG-pulsed DC may prove to be a new and further tool to add to those designed.