The outcome of natural infections with pathogenic mycobacteria can range from early asymptomatic clearance through latent infection to clinical disease. Different host and pathogen-specific factors have been implicated in determining the outcome of these infections; however, it is clear that the interaction of mycobacteria with the innate and acquired components of the immune system plays a central role. Specifically, the recognition of mycobacterial components by innate immune cells through different pathogen recognition receptors (PPRs) induces a cytokine response that can promote early control of the infection. In fact, in the majority of individuals that come into contact with mycobacteria, this response is enough to control the infection. Among PRRs, Toll-like receptors (TLRs), Nucleotide Oligomerization Domain (NOD)-like receptors, and C-type lectins have all been implicated in recognition of mycobacteria and in the initiation of the cytokine response. Defining the mechanisms by which distinct mycobacterial components and their receptors stimulate the immune response is an area of intense research.