Information from comparative proteome analysis of Mycobacterium tuberculosis and Mycobacterium bovis bacillus Calmette-Guérin (BCG) principally allows prediction of potential vaccine candidates. Thirty-six M. tuberculosis DNA vaccine candidates identified by comparative proteome analysis were evaluated in the mouse model for protection against low-dose aerosol M. tuberculosis infection. We identified the DNA vaccine candidate Rv3407 as a protective antigen and analyzed putative major histocompatibility complex class I epitopes by computational predictions and gamma interferon Elispot assays. Importantly, we discovered that the DNA vaccine Rv3407 improved the efficacy of BCG vaccination in a heterologous prime-boost vaccination protocol. Our data demonstrate the rationale of a combination of proteomics, epitope prediction, and broad screening of putative antigens for identification of novel DNA vaccine candidates. Furthermore, our experiments show that heterologous prime-boost vaccination with a defined antigen boost “on top” of a BCG primer provides superior protection against tuberculosis over vaccination with BCG alone.