In silico analysis reveals that most protective antigens expressed by the antituberculous vaccine Mycobacterium bovis BCG (BCG) are conserved in M. avium, supporting the hypothesis that exposure to environmental mycobacteria generates cross-reactive immune responses blocking BCG activity. We investigated the impact of sensitization with M. avium, M. scrofulaceum, or M. vaccae on the protective efficacy of a recombinant BCG strain expressing RD1 antigens (BCG::RD1), using a mouse model of experimental tuberculosis (TB). No evidence that the RD1-encoded antigens ESAT-6, CFP-10, and PPE68 were expressed by these environmental strains could be demonstrated by Western blot analysis. Mice sensitized with each of these strains did not prime cellular immune responses cross-reacting with the immunodominant ESAT-6. Importantly, clearance of BCG::RD1 from the lungs and spleens of mice exposed to each of the environmental strains before vaccination was minimal compared to that of BCG. In mice sensitized with M. avium, increased persistence of BCG::RD1 correlated with stronger antimycobacterial gamma interferon responses and enhanced protection against aerosol infection with M. tuberculosis, compared to BCG. In contrast, animals exposed to M. scrofulaceum or M. vaccae prior to vaccination with BCG or BCG::RD1 were better protected against TB than were the unsensitized controls. Our results suggest that the inhibitory effect of environmental mycobacteria on the protective efficacy of BCG depends critically on the extent of cross-recognition of antigens shared with the vaccine. In hosts sensitized with M. avium, potent immunogenicity of ESAT-6 and increased persistence of BCG::RD1 may allow this recombinant vaccine to overcome preexisting antimycobacterial responses.