There is an urgent need to develop vaccines that can elicit immunological memory responses against HIV. Using the rhesus macaque model and a combination of intranasal (IN) and parenteral immunizations with DNA or protein adsorbed to microparticles or mixed with mucosal adjuvants we sought to induce anti-HIV memory-type immune responses in both the mucosal and systemic compartments. Prime/boost immunizations were performed through five IN immunizations alone with HIV-env oligomeric gp140 (Ogp140) or HIV-gag-p24 mixed with Escherichia coli heat labile-derived mutant adjuvants or two parenteral immunizations with DNA encoding HIV-env or -gag adsorbed to microparticles followed by three IN immunizations with p24 gag protein and the mutant adjuvants. Both modes of immunizations induced anti-gp140 plasma and vaginal IgG and IgA as well as interferon (IFN)-gamma secreting peripheral blood mononuclear cells (PBMC) after HIV-env and -gag peptide restimulation. After a resting period of 4 months, when the levels of humoral and cellular responses had decreased, intramuscular (IM) booster immunizations with p55-gag protein adsorbed to microparticles and Ogp140 in MF59 oil in water emulsion significantly enhanced anti-HIV plasma and vaginal antibody, as well as peripheral blood IFN-gamma responses in all groups of vaccinated macaques. Importantly, plasma neutralization activity against both homologous and heterologous HIV strains was observed in all groups following the IM booster immunizations with protein. These findings show that IN priming alone or combinations of parenteral and IN immunizations followed by IM booster immunizations hold promise to significantly enhance mucosal and systemic memory-type immune responses against HIV-1 antigens.