None of the currently available distemper vaccines provides a satisfactory solution for the immunization of very young carnivores in the face of maternal-derived immunity. Since mucosal immunization with replication-competent adenovirus-based vaccines has been proven effective in the face of passive immunity against the vector, it has the potential to provide a solution for the vaccination of young puppies born to canine distemper virus (CDV)-immune dams. We report the engineering and the characterization of two replication-competent canine adenovirus type 2 (CAV2)-based vaccines expressing, respectively, the CDV hemagglutinin (HA) and fusion (F) antigens. We first demonstrated that the intranasal vaccination with a mixture of both recombinant CAV2s provides an excellent level of protection in seronegative puppies, confirming the value of replication-competent adenovirus-based vectors for mucosal vaccination. In contrast, intranasal immunization with the same vaccine of puppies born to CDV- and CAV2-immune dams, failed to activate specific and protective immune responses. We hypothesized that an active CAV2 infection occurred while puppies were in close contact with the vaccinated dams in the breeding units and that the resulting active mucosal immunity interfered with the intranasal administration of CAV2-based CDV vaccine. However, when puppies born to CDV- and CAV2-immune dams were vaccinated subcutaneously with the CAV2-based CDV vaccine, significant seroconversion and solid protective immunity were triggered despite pre-existing systemic immunity to the vector. This latter result is surprising and suggests that subcutaneous vaccination with a replication-competent recombinant CAV2 may be an efficient strategy to overcome both passive and active adenovirus specific immunity in the dog. From a practical point of view, this could pave the way for an original strategy to vaccinate young puppies in the face of maternal-derived immunity.