The host response to mycobacterial infection depends on host and pathogen genetic factors. Recent studies in human populations suggest a strain specific genetic control of tuberculosis. To test for mycobacterial-strain specific genetic control of susceptibility to infection under highly controlled experimental conditions, we performed a comparative genetic analysis using the A/J- and C57BL/6J-derived recombinant congenic (RC) mouse panel infected with the Russia and Pasteur strains of Mycobacterium bovis Bacille Calmette Guérin (BCG). Bacillary counts in the lung and spleen at weeks 1 and 6 post infection were used as a measure of susceptibility. By performing genome-wide linkage analyses of loci that impact on tissue-specific bacillary burden, we were able to show the importance of correcting for strain background effects in the RC panel. When linkage analysis was adjusted on strain background, we detected a single locus on chromosome 11 that impacted on pulmonary counts of BCG Russia but not Pasteur. The same locus also controlled the splenic counts of BCG Russia but not Pasteur. By contrast, a locus on chromosome 1 which was indistinguishable from Nramp1 impacted on splenic bacillary counts of both BCG Russia and Pasteur. Additionally, dependent upon BCG strain, tissue and time post infection, we detected 9 distinct loci associated with bacillary counts. Hence, the ensemble of genetic loci impacting on BCG infection revealed a highly dynamic picture of genetic control that reflected both the course of infection and the infecting strain. This high degree of adaptation of host genetics to strain-specific pathogenesis is expected to provide a suitable framework for the selection of specific host-mycobacteria combinations during co-evolution of mycobacteria with humans.