Genes modulating innate immunity in mammals are generally considered the first line of defense with respect to invading pathogens and therefore it has become important to characterize naturally occurring genetic variation, and subsequently determine whether this variation is likely to be benign, beneficial, or detrimental to the host. Relevant to this study, the mammalian Toll-like receptor proteins (TLR), encoded by members of the TLR gene family, have the capacity to recognize a wide variety of pathogen ligands, and mutations within these genes have been shown to influence disease susceptibility or resistance within mammalian species. Two studies which sought to determine the frequency and distribution of naturally occurring genetic variation within the bovine and equine TLR genes revealed a large number of discrete point mutations, which were subsequently used to reconstruct haplotypes for each investigated gene across a large number of samples. Detailed analyses of haplotypes provided evidence for extensive haplotype sharing among specialized breeds, subspecies, and even divergent species. Classical and new tests of selection provided evidence for significant deviations from a strictly neutral model of molecular evolution for both cattle as well as equids, with some of the same TLR genes deviating from a strictly neutral model among divergent species. As a first step toward determining whether naturally occurring bovine TLR variation is likely to be benign, beneficial, or detrimental, we tested validated variation from bovine TLR genes capable of recognizing components of Mycobacteria for associations with Mycobacterium avium subspecies paratuberculosis (MAP) infection in dairy cattle, and found several SNPs that were nominally associated with disease status, thereby providing evidence for small-effect loci potentially influencing risk for differential susceptibility to Johne's disease.