Pulmonary tuberculosis remains a major health problem. Effective vaccination strategies are urgently needed. It was previously demonstrated that purified Mycobacterium bovis BCG Heparin Binding Haemagglutinin (HBHA) is able to induce in BALB/c mice protection levels against a Mycobacterium tuberculosis infection that are similar to those offered by BCG. Here we developed a heterologous prime/boost immunisation approach using a combination of BCG and HBHA in order to increase the protective immune response. We show that the time period between BCG priming and HBHA boosting strongly influences the efficacy of the boost. The optimized vaccine protocol consisting of a BCG administration followed 8 months later by boosting with HBHA resulted in an increase in the level of protection of up to 0.7log when compared to BCG alone. These results suggest an immunisation strategy where BCG is administered to neonates and is followed by subcutaneous HBHA boosting in young adults.