Gut-associated lymphoid tissue (GALT) is the primary replication site for HIV-1, resulting in a pronounced CD4(+) T cell loss in this tissue during primary infection. A mucosal vaccine that generates HIV-specific CD8(+) T cells in the gut could prevent the establishment of founder populations and broadcasting of virus. Here, we immunized mice orally and systemically with a chimpanzee derived adenoviral vector expressing HIV gag (AdC68gag) and measured frequencies of gag-specific interferon-gamma (IFN-gamma) producing CD8(+) T cells in the GALT. A single oral administration was inefficient at eliciting responses in the mesenteric lymph nodes and Peyer's Patches, while a single intramuscular administration elicited strong systemic and detectable mucosal responses. The gag-specific CD8(+) T cell responses were present in both acute and memory phases following intramuscular administration.