Johne's disease, caused by Mycobacterium avium subspecies paratuberculosis (Map), is a fatal disease in cattle. The objective of this study was to identify loci associated with tolerance in cows infected with Map. Tolerance was defined as a cow's fitness at a given level of Map infection intensity. Fitness was measured by Map faecal cultures, and Map infection intensity was measured by culturing four gut tissues. The quantitative phenotype of tolerance was defined by numerical indexes of cultures of peak (peak tolerance, PT) and average (average tolerance, AT) faecal and tissue Map from 245 Holstein cows. The categorical phenotype was defined as: ≥ 100 cfu Map tissue infection, and faecal shedding ≥ 75 cfu (intolerant) or <10 cfu (tolerant cows). In 94 cows, Map was identified in ≥ 1 tissue, including 44 cows with ≥ 100 Map tissue cfu and 36 with ≥ 1 faecal cfu. A genome-wide association analysis was performed after filtering, leaving genotypes for 45,789 SNPs in 90 animals for the quantitative phenotype and 16 cases and 25 controls for the categorical analysis of tolerance. rs41748405:A>C (BTA15) was associated with PT (P = 1.12 × 10(-7)) and AT (P = 2.17 × 10(-6)). Associations were identified with PT and adjacent SNPs ss61512613:A>G and ss61530518:A>G (BTA6) (P < 3.0 × 10(-5)), and with AT for ss61469568:A>G (BTA 2) (P = 3.3 × 10(-5)) and ss86284768:A>G (BTA1) (P = 3.31 × 10(-5)). For the categorical phenotype, an association was found with ss8632653:A>G (BTA6) (P < 5.0 × 10(-5)). This is the first study to identify loci associated with tolerance to Johne's disease.