Live attenuated vaccine vectors based on recombinant vesicular stomatitis virus (VSV) are effective in several viral disease models. In this study, we asked if a VSV vector capable of only a single cycle of replication might be an effective alternative to replication-competent VSV vectors. We compared the cellular immune responses to human immunodeficiency virus (HIV) envelope protein (Env) expressed by replication-competent and single-cycle VSV vectors and also examined the antibody response to Env. The single-cycle vector was grown by complementation with VSV G protein and then tested initially for immunogenicity when given by four different routes. When given by the intramuscular route in mice, we found that the single-cycle vector was equivalent to the replication-competent VSV vector in generating high-level primary and memory CD8 T-cell responses as well as antibody responses to Env. Cellular responses were analyzed using major histocompatibility complex class I tetramers and direct measurement of cytotoxic T-lymphocyte activity in vivo. We also found that the recall responses after boosting were equivalent in animals vaccinated with replication-competent or single-cycle vectors. Additionally, we observed recall and heightened memory responses after boosting animals with a single-cycle vector complemented with G protein from a different vesiculovirus. Because expression of HIV Env by G-deleted VSV might allow replication in human cells expressing CD4, we generated a single-cycle VSV recombinant expressing a secreted form of the HIV Env protein. This virus was just as effective as the recombinant expressing the membrane-anchored Env protein at producing CD8 T cells and antibody responses.