The emergence of novel influenza viruses that cause devastating human disease is an ongoing threat and serves as an impetus for the continued development of novel approaches to influenza vaccines. Influenza vaccine development has traditionally focused on producing humoral and/or cell-mediated immunity, often against the viral surface glycoproteins hemagglutinin (HA) and neuraminidase (NA). Here, we describe a new vaccine candidate that utilizes a replication-defective vesicular stomatitis virus (VSV) vector backbone that lacks the native G surface glycoprotein gene (VSVΔG). The expression of the H5 HA of an H5N1 highly pathogenic avian influenza virus (HPAIV), A/Vietnam/1203/04 (VN1203), and the NA of the mouse-adapted H1N1 influenza virus A/Puerto Rico/8/34 (PR8) in the VSVΔG vector restored the ability of the recombinant virus to replicate in cell culture, without the requirement for the addition of trypsin. We show here that this recombinant virus vaccine candidate was non-pathogenic in mice when given by either the intramuscular or intranasal route of immunization and that the in vivo replication of VSVΔG-H5N1 is profoundly attenuated. This recombinant virus also provided protection against lethal H5N1 infection after a single dose. This novel approach to vaccination against HPAIVs may be widely applicable to other emerging strains of influenza virus.