The mucosal immune system acts as a first line of defense against infection caused by luminal pathogens. Because HIV is transmitted primarily via mucosal-associated tissues, particularly with sexual transmission, understanding antiviral immunity present at these sites is important. HIV infection results in depletion of gut-associated lymphoid tissue (GALT) and in this sense can be considered to be a disease of the mucosal immune system. A stumbling block for efforts to develop a vaccine against this disease has been the escape of vaccine-induced neutralizing antibodies and cytotoxic T lymphocytes (CTLs) at mucosal compartments and the resulting viral spread. To avoid these problems, the ideal mucosal vaccine would induce HIV-specific secretory IgA (S-IgA) and mucosal CD8(+) CTL as a first line of defense at a very early stage of HIV infection, before the virus can seed into the secondary lymphoid organs in mucosal and systemic tissues. In this review, we provide an overview of mucosal vaccine concepts and vaccination strategies that have been proposed for the development of an HIV mucosal vaccine, including live recombinant vaccines, peptide-based vaccines, virus-like particles (VLP), subunit vaccines and DNA vaccines.