Flagellin has been tested as a protein-based vaccine adjuvant, with the majority of studies focused on antibody responses. Here, we evaluated the adjuvant activity of flagellin for both cellular and humoral immune responses in BALB/c mice in the setting of gene-based immunization, and have made several novel observations. DNA vaccines and adenovirus (Ad) vectors were engineered to encode mycobacterial protein Ag85B, with or without flagellin of Salmonella typhimurium (FliC). DNA-encoded flagellin given IM enhanced splenic CD4+ and CD8+ T cell responses to co-expressed vaccine antigen, including memory responses. Boosting either IM or intranasally with Ad vectors expressing Ag85B without flagellin led to durable enhancement of Ag85B-specific antibody and CD4+ and CD8+ T cell responses in both spleen and pulmonary tissues, correlating with significantly improved protection against challenge with pathogenic aerosolized M. tuberculosis. However, inclusion of flagellin in both DNA prime and Ad booster vaccines induced localized pulmonary inflammation and transient weight loss, with route-dependent effects on vaccine-induced T cell immunity. The latter included marked reductions in levels of mucosal CD4+ and CD8+ T cell responses following IM DNA/IN Ad mucosal prime-boosting, although antibody responses were not diminished. These findings indicate that flagellin has differential and route-dependent adjuvant activity when included as a component of systemic or mucosally-delivered gene-based prime-boost immunization. Clear adjuvant activity for both T and B cell responses was observed when flagellin was included in the DNA priming vaccine, but side effects occurred when given in an Ad boosting vector, particularly via the pulmonary route.