Mycobacterium tuberculosis (Mtb) is the leading cause of death from infection worldwide. The only available vaccine, BCG (Bacillus Calmette-Guérin), is given intradermally and has variable efficacy against pulmonary tuberculosis, the major cause of mortality and disease transmission. Here we show that intravenous administration of BCG profoundly alters the protective outcome of Mtb challenge in non-human primates (Macaca mulatta). Compared with intradermal or aerosol delivery, intravenous immunization induced substantially more antigen-responsive CD4 and CD8 T cell responses in blood, spleen, bronchoalveolar lavage and lung lymph nodes. Moreover, intravenous immunization induced a high frequency of antigen-responsive T cells across all lung parenchymal tissues. Six months after BCG vaccination, macaques were challenged with virulent Mtb. Notably, nine out of ten macaques that received intravenous BCG vaccination were highly protected, with six macaques showing no detectable levels of infection, as determined by positron emission tomography-computed tomography imaging, mycobacterial growth, pathology and granuloma formation. The finding that intravenous BCG prevents or substantially limits Mtb infection in highly susceptible rhesus macaques has important implications for vaccine delivery and clinical development, and provides a model for defining immune correlates and mechanisms of vaccine-elicited protection against tuberculosis.