Johne's disease or paratuberculosis, caused by Mycobacterium avium subsp. paratuberculosis (MAP), occurs in domestic and wild animals worldwide, causing a significant economic loss to livestock industries. After a prolonged incubation time, infected cattle shed MAP bacilli into feces and spread the disease to an uninfected animal population. It is largely unknown how (or whether) the interplay between the pathogen and the host immunity determines timing of shedding after the long incubation time. Such information would provide an understanding of pathogenesis in individual animals and the epidemiology of MAP infection in animal populations. In this review, we summarize current knowledge of bovine Johne's disease pathology, pathogenesis, immunology and genetics. We discuss knowledge gaps that direly need to be addressed to provide a science-based approach to diagnostics and (immuno)prophylaxis. These knowledge gaps are related to anatomical/clinical manifestation of MAP invasion, interaction of bacteria with phagocytes, granuloma formation, shedding, establishment and kinetics of adaptive immune responses in the pathogenesis of the disease. These topics are discussed at the molecular, cellular and tissue levels with special attention to the within host dynamics including the temporal and the spatial context relevant for the various host-pathogen interactions.