Virulent mycobacterial infections progress slowly, with a latent period that leads to clinical disease in a proportion of cases. Mycobacterium avium subsp. paratuberculosis is an intracellular pathogen that causes paratuberculosis or Johne's disease (JD), a chronic intestinal disease of ruminants. Indoleamine 2,3-dioxygenase (IDO), an enzyme that regulates tryptophan metabolism, was originally reported to have a role in intracellular pathogen killing and has since been shown to have an important immunoregulatory role in chronic immune diseases. Here we demonstrate an association between increased IDO levels and progression to clinical mycobacterial disease in a natural host, characterizing gene expression, protein localization, and functional effects. IDO mRNA levels were significantly increased in M. avium subsp. paratuberculosis-infected monocytic cells. Levels of both IDO gene and protein expression were significantly upregulated within the affected tissues of sheep with JD, particularly at the site of primary infection, the ileum, of animals with severe multibacillary disease. Lesion severity was correlated with the level of IDO gene expression. IDO gene expression was also increased in the peripheral blood cells of M. avium subsp. paratuberculosis-exposed sheep and cattle. IDO breaks down tryptophan, and systemic increases were functional, as shown by decreased plasma tryptophan levels, which correlated with the onset of clinical signs, a stage well known to be associated with Th1 immunosuppression. IDO may be involved in downregulating immune responses to M. avium subsp. paratuberculosis and other virulent mycobacteria, which may be an example of the pathogen harnessing host immunoregulatory pathways to aid survival. These findings raise new questions about the host-mycobacterium interactions in the progression from latent to clinical disease.