Vaccination is the most cost effective control measure for Johne's disease caused by Mycobacterium avium subspecies paratuberculosis (MAP) but currently available whole cell killed formulations have limited efficacy and are incompatible with the diagnosis of bovine tuberculosis by tuberculin skin test. We have evaluated the utility of a viral delivery regimen of non-replicative human Adenovirus 5 and Modified Vaccinia virus Ankara recombinant for early entry MAP specific antigens (HAV) to show protection against challenge in a calf model and extensively screened for differential immunological markers associated with protection. We have shown that HAV vaccination was well tolerated, could be detected using a differentiation of infected and vaccinated animals (DIVA) test, showed no cross-reactivity with tuberculin and provided a degree of protection against challenge evidenced by a lack of faecal shedding in vaccinated animals that persisted throughout the 7 month infection period. Calves given HAV vaccination had significant priming and boosting of MAP derived antigen (PPD-J) specific CD4+, CD8+ IFN-γ producing T-cell populations and, upon challenge, developed early specific Th17 related immune responses, enhanced IFN-γ responses and retained a high MAP killing capacity in blood. During later phases post MAP challenge, PPD-J antigen specific IFN-γ and Th17 responses in HAV vaccinated animals corresponded with improvements in peripheral bacteraemia. By contrast a lack of IFN-γ, induction of FoxP3+ T cells and increased IL-1β and IL-10 secretion were indicative of progressive infection in Sham vaccinated animals. We conclude that HAV vaccination shows excellent promise as a new tool for improving control of MAP infection in cattle.