Mycobacterium avium ssp. paratuberculosis (MAP) causes chronic enteritis in cattle that results in substantial financial losses to the cattle industry worldwide. Given that susceptibility to MAP infection is determined in part by genetics, marker-assisted selection may help in the breeding of animals that are more resistant to MAP infection. The toll-like receptor 4 gene (TLR4) was selected as a potential candidate gene because of its role in innate immunity and its involvement in MAP recognition and infection. The objective of this study, therefore, was to identify associations between TLR4 polymorphisms and susceptibility to MAP infection in Canadian Holstein cows. Two biologically relevant SNPs, including c.-226G>C in the 50 -untranslated region and the non-synonymous SNP c.2021C>T in the potential TIR domain, were selected for an association analysis with MAP infection status in 409 Canadian Holsteins. The haplotype C-T from these combined SNPs yielded significant association with susceptibility to MAP infection, supporting the involvement of TLR4 in susceptibility to MAP infection.