Cholesterol plays an important role in the establishment of mycobacterial infections. Mycobacterial species such as Mycoacterium tuberculosis are capable of utilising cholesterol as a primary energy source in culture. M. leprae localises to cholesterol-rich areas of an infected cell, which holds significance for the intracellular niches created by mycobacteria. Despite the implications for other mycobacterial species, there has been very little research examining the relationship between cholesterol and Mycobacterium avium subsp. paratuberculosis (MAP). This study examined the role of both serum and intracellular cholesterol during the early stages of MAP infection in both sheep and cattle in vivo and in vitro. Using a well-established infection model, sheep and cattle were exposed to MAP and blood and faecal samples were collected at monthly intervals. Total serum cholesterol changed significantly in exposed animals during the first few months of infection in both sheep and cattle when compared to the control cohorts. In in vitro infection experiments using monocytes from MAP non-exposed cattle and sheep and fluorescent microscopic techniques demonstrated that GFP-tagged MAP co-localised to cholesterol-rich domains within the cell. In addition, changes in the expression of a number of cholesterol-associated genes within the macrophage suggest that MAP is capable of altering cholesterol metabolism of the infected cell. Thus previously unexplored mechanisms within the intracellular environment created by MAP during the early stages of infection may be important for understanding the survival and persistence of MAP.