The immune system is not always successful in recognizing and destroying pathogens it may encounter. Host immunity to mycobacteria is characterized by a very complex series of events, designed to clear the infection. The first line of defense is uptake and processing of the pathogen by macrophages, followed by the initiation of cell-mediated immunity. The secretion of pro-inflammatory cytokines such as IFN-γ is credited with containment of mycobacterial infections. Yet it is clear that activated T-cells may contain but fail to clear the infection in some hosts. Further, it is recognized that if infection progresses to a more clinical state, the production of pro-inflammatory cytokines is suppressed and expression of anti-inflammatory cytokines is increased. It is unclear what defines a host that can successfully contain the infection versus one that succumbs to severe immunopathologic disease. This review will address some of the key elements in host immunity to mycobacterial pathogens, with an emphasis on Mycobacterium avium subsp. paratuberculosis (M. paratuberculosis), in an attempt to understand the dialogue between immune cells and their mediators during infection and what causes this discourse to go awry.