Each year, approximately five million people die worldwide from putatively vaccine-preventable mucosally transmitted diseases. With respect to mass vaccination campaigns, one strategy to cope with this formidable challenge is aerosol vaccine delivery, which offers potential safety, logistical, and cost-saving advantages over traditional vaccination routes. Additionally, aerosol vaccination may elicit pivotal mucosal immune responses that could contain or eliminate mucosally transmitted pathogens in a preventative or therapeutic vaccine context. In this current preclinical non-human primate investigation, we demonstrate the feasibility of aerosol vaccination with the recombinant poxvirus-based vaccine vectors NYVAC and MVA. Real-time in vivo scintigraphy experiments with radiolabeled, aerosol-administered NYVAC-C (Clade C, HIV-1 vaccine) and MVA-HPV vaccines revealed consistent mucosal delivery to the respiratory tract. Furthermore, aerosol delivery of the vaccines was safe, inducing no vaccine-associated pathology, in particular in the brain and lungs, and was immunogenic. Administration of a DNA-C/NYVAC-C prime/boost regime resulted in both systemic and anal-genital HIV-specific immune responses that were still detectable 5 months after immunization. Thus, aerosol vaccination with NYVAC and MVA vectored vaccines constitutes a tool for large-scale vaccine efforts against mucosally transmitted pathogens.