The induction of a potent humoral and cellular immune response in mucosal tissue is important for the development of an effective HIV vaccine. Most of the current HIV vaccines under development use the i.m. route for immunization, which is relatively poor in generating potent and long-lived mucosal immune responses. In this article, we explore the ability of an oral vaccination with a probiotic organism, Lactococcus lactis, to elicit HIV-specific immune responses in the mucosal and systemic compartments of BALB/c mice. We expressed the HIV-1 Gag-p24 on the tip of the T3 pilus of Streptococcus pyogenes as a fusion to the Cpa protein (LL-Gag). After four monthly LL-Gag oral immunizations, we observed strong Gag-specific IgG and IgA responses in serum, feces, and vaginal secretions. However, the Gag-specific CD8 T cell responses in the blood were at or below our detection limit. After an i.m. modified vaccinia Ankara/Gag boost, we observed robust Gag-specific CD8 T cell responses both in systemic and in mucosal tissues, including intraepithelial and lamina propria lymphocytes of the small intestine, Peyer's patches, and mesenteric lymph nodes. Consistent with strong immunogenicity, the LL-Gag induced activation of CD11c(+) CD11b(+) dendritic cells in the Peyer's patches after oral immunization. Our results demonstrate that oral immunization with L. lactis expressing an Ag on the tip of the group A Streptococcus pilus serves as an excellent vaccine platform to induce strong mucosal humoral and cellular immunity against HIV.