Infection with Mycobacterium avium subsp. paratuberculosis causes Johne's disease in cattle and is a serious problem for the dairy industry worldwide. Development of models to mimic aspects of Johne's disease remains an elusive goal because of the chronic nature of the disease. In this report, we describe a surgical approach employed to characterize the very early stages of infection of calves with M. avium subsp. paratuberculosis. To our surprise, strains of M. avium subsp. paratuberculosis were able to traverse the intestinal tissues within 1 h of infection in order to colonize distant organs, such as the liver and lymph nodes. Both the ileum and the mesenteric lymph nodes were persistently infected for months following intestinal deposition of M. avium subsp. paratuberculosis despite a lack of fecal shedding of mycobacteria. During the first 9 months of infection, humoral immune responses were not detected. Nonetheless, using flow cytometric analysis, we detected a significant change in the cells participating in the inflammatory responses of infected calves compared to cells in a control animal. Additionally, the levels of cytokines detected in both the ileum and the lymph nodes indicated that there were TH1-type-associated cellular responses but not TH2-type-associated humoral responses. Finally, surgical inoculation of a wild-type strain and a mutant M. avium subsp. paratuberculosis strain (with an inactivated gcpE gene) demonstrated the ability of the model which we developed to differentiate between the wild-type strain and a mutant strain of M. avium subsp. paratuberculosis deficient in tissue colonization and invasion. Overall, novel insights into the early stages of Johne's disease were obtained, and a practical model of mycobacterial invasiveness was developed. A similar approach can be used for other enteric bacteria.