Human adenoviruses (AdVs) are one of the most common causes of acute respiratory viral infections worldwide. Multiple AdV serotypes with low cross-reactivity circulate in the human population, making the development of an effective vaccine very challenging. In the current study, we designed a cross-reactive AdV vaccine based on the T-cell epitopes conserved among various AdV serotypes, which were inserted into the genome of a licensed cold-adapted live attenuated influenza vaccine (LAIV) backbone. We rescued two recombinant LAIV-AdV vaccines by inserting the selected AdV T-cell epitopes into the open reading frame of full-length NA and truncated the NS1 proteins of the H7N9 LAIV virus. We then tested the bivalent vaccines for their efficacy against influenza and human AdV5 in a mouse model. The vaccine viruses were attenuated in C57BL/6J mice and induced a strong influenza-specific antibody and cell-mediated immunity, fully protecting the mice against virulent influenza virus infection. The CD8 T-cell responses induced by both LAIV-AdV candidates were functional and efficiently killed the target cells loaded either with influenza NP366 or AdV DBP418 peptides. In addition, high levels of recall memory T cells targeted to an immunodominant H2b-restricted CD8 T-cell epitope were detected in the immunized mice after the AdV5 challenge, and the magnitude of these responses correlated with the level of protection against pulmonary pathology caused by the AdV5 infection. Our findings suggest that the developed recombinant vaccines can be used for combined protection against influenza and human adenoviruses and warrant further evaluation on humanized animal models and subsequent human trials. © 2020 by the authors. Licensee MDPI, Basel, Switzerland.