Recombinant rhabdovirus vectors expressing human immunodeficiency virus (HIV) and/or simian immunodeficiency virus (SIV) proteins have been shown to induce strong immune responses in mice and rhesus macaques. However, the finding that such responses protect rhesus macaques from AIDS-like disease but not from infection indicates that further improvements for these vectors are needed. Here, we designed a prime-boost schedule consisting of a rabies virus (RV) vaccine strain and a recombinant vesicular stomatitis virus (VSV) both expressing HIV Envelope (Env). Mice were primed and boosted with the two vaccine vehicles by different routes and in different combinations. Mucosal and systemic humoral responses were assessed using enzyme linked immunosorbent assay (ELISA) while the cellular immune response was determined by an IFN-gamma ELISPOT assay. We found that an immunization combination of RV and VSV elicited the highest titers of anti-Env antibodies and the greatest amount of Env-specific IFN-gamma secreting cells pre- and post-challenge with a recombinant vaccinia virus expressing HIV(89.6) Env. Furthermore, intramuscular immunization did not induce antigen-specific mucosal antibodies while intranasal inoculation stimulated vector-specific IgA antibodies in vaginal washings and serum. Our results show that it is feasible to elicit robust cellular and humoral anti-HIV responses using two different live attenuated Rhabdovirus vectors to sequentially prime and boost.