Abstract Stimulation of tumor-specific responses in both CD4+ and CD8+ T cells has been a challenge for effective tumor vaccines. We designed a vaccine vector containing the AIDA-1 autotransporter and DNA vaccine elements, generating a murine melanoma vaccine that was delivered by the attenuated Salmonella strain SL7207. Growth of murine subcutaneous melanoma was significantly inhibited by intranasal immunization with the Salmonella tumor vaccine. The vaccine activated tumor-specific CD4+ and CD8+ T-cell responses, with increased T-cell proliferation, tumor antigen–specific Th1 cytokine production, increased percentages of tetramer positive cells, and cytotoxicity. CD4+ or CD8+ T-cell depletion resulted in the loss of antitumor activity of the Salmonella tumor vaccine, suggesting that the efficacy of the vaccine was dependent on both CD4+ and CD8+ T cells. Lung metastasis of the tumor was also inhibited by vaccine treatment. Similarly, the percentages of tumor-specific Th1 cytokine production by CD4+ and CD8+ T cells in the spleen, tumor, and bronchoalveolar lavage were increased after vaccine treatment. Tumor-specific proliferation of CD4+ and CD8+ T cells was also promoted by the vaccine. Tetramer staining and cytotoxicity assay showed enhanced tumor-specific CD8+ T-cell response after vaccine treatment. Therefore, the Salmonella tumor vaccine could activate both tumor-specific CD4+ and CD8+ T-cell responses. This vaccine strategy may be widely applicable to the development of oral or nasal vaccines against tumors. Cancer Immunol Res; 5(6); 503–14. ©2017 AACR.