Given the lethality of H5N1 avian influenza viruses (AIV) and the recurring spread from poultry to humans, an effective vaccine against H5N1 viruses may be needed to prevent a pandemic. We generated experimental vaccine vectors based on recombinant vesicular stomatitis virus (VSV) expressing the H5 hemagglutinin (HA) from an H5N1 virus isolated in 1997. The HA gene was expressed either from an attenuated wild-type VSV vector or from a single-cycle vector containing a deletion of the VSV G gene. We found that all of the vectors induced potent neutralizing antibody titers against the homologous and antigenically heterologous H5N1 viruses isolated in 2004 and 2005. Vaccination of mice with any combination of prime or prime/boost vectors provided long-lasting protection (>7 months) against challenge with AIV, even in animals receiving a single dose of single-cycle vaccine. Our data indicate that these recombinants are promising vaccine candidates for pandemic influenza.