Background: BCG, the only licensed vaccine against tuberculosis, provides some protection against disseminated disease in infants but has little effect on prevention of adult pulmonary disease. Newer parenteral immunization prime boost regimes may provide improved protection in experimental animal models but are unproven in man so that there remains a need for new and improved immunization strategies. Methods and Findings: Mice were immunized parenterally, intranasally or simultaneously by both routes with BCG or recombinant mycobacterial antigens plus appropriate adjuvants. They were challenged with Mycobacterium tuberculosis (Mtb) and the kinetics of Mtb growth in the lungs measured. We show that simultaneous immunization (SIM) of mice by the intranasal and parenteral routes is highly effective in increasing protection over parenteral BCG administration alone. Intranasal immunization induces local pulmonary immunity capable of inhibiting the growth of Mtb in the early phase (the first week) of infection, while parenteral immunization has a later effect on Mtb growth. Importantly, these two effects are additive and do not depend on priming and boosting the immune response. The best SIM regimes reduce lung Mtb load by up to 2 logs more than BCG given by either route alone. Conclusions: These data establish SIM as a novel and highly effective immunization strategy for Mtb that could be carried out at a single clinic visit. The efficacy of SIM does not depend on priming and boosting an immune response, but SIM is complementary to prime boost strategies and might be combined with them.