In spite of several attempts over many years at developing a HIV vaccine based on classical strategies, none has convincingly succeeded to date. As HIV is transmitted primarily by the mucosal route, particularly through sexual intercourse, understanding antiviral immunity at mucosal sites is of major importance. An ideal vaccine should elicit HIV-specific antibodies and mucosal CD8+ cytotoxic T-lymphocyte (CTL) as a first line of defense at a very early stage of HIV infection, before the virus can disseminate into the secondary lymphoid organs in mucosal and systemic tissues. A primary focus of HIV preventive vaccine research is therefore the induction of protective immune responses in these crucial early stages of HIV infection. Numerous approaches are being studied in the field, including building upon the recent RV144 clinical trial. In this article, we will review current strategies and briefly discuss the use of adjuvants in designing HIV vaccines that induce mucosal immune responses.