Neonates and juvenile ruminants are very susceptible to paratuberculosis infection. This is likely due to a high degree of exposure from their dams and an immature immune system. To test the influence of age on vaccine-induced responses, a cocktail of recombinant Mycobacterium avium subsp. paratuberculosis proteins (MAP0217, MAP1508, MAP3701c, MAP3783, and MAP1609c/Ag85B) was formulated in a cationic liposome adjuvant (CAF01) and used to vaccinate animals of different ages. Male jersey calves were divided into three groups that were vaccinated at 2, 8, or 16 weeks of age and boosted twice at weeks 4 and 12 relative to the first vaccination. Vaccine-induced immune responses, the gamma interferon (IFN-γ) cytokine secretion and antibody responses, were followed for 20 weeks. In general, the specific responses were significantly elevated in all three vaccination groups after the first booster vaccination with no or only a minor effect from the second booster. However, significant differences were observed in the immunogenicity levels of the different proteins, and it appears that the older age group produced a more consistent IFN-γ response. In contrast, the humoral immune response is seemingly independent of vaccination age as we found no difference in the IgG1 responses when we compared the three vaccination groups. Combined, our results suggest that an appropriate age of vaccination should be considered in vaccination protocols and that there is a possible interference of vaccine-induced immune responses with weaning (week 8).