A safe and effective vaccine is the best way to prevent large-scale highly pathogenic avian influenza virus (HPAI) H5N1 outbreaks in the human population. The current FDA-approved H5N1 vaccine has serious limitations. A more efficacious H5N1 vaccine is urgently needed. Parainfluenza virus 5 (PIV5), a paramyxovirus, is not known to cause any illness in humans. PIV5 is an attractive vaccine vector. In our studies, a single dose of a live recombinant PIV5 expressing a hemagglutinin (HA) gene of H5N1 (rPIV5-H5) from the H5N1 subtype provided sterilizing immunity against lethal doses of HPAI H5N1 infection in mice. Furthermore, we have examined the effect of insertion of H5N1 HA at different locations within the PIV5 genome on the efficacy of a PIV5-based vaccine. Interestingly, insertion of H5N1 HA between the leader sequence, the de facto promoter of PIV5, and the first viral gene, nucleoprotein (NP), did not lead to a viable virus. Insertion of H5N1 HA between NP and the next gene, V/phosphorprotein (V/P), led to a virus that was defective in growth. We have found that insertion of H5N1 HA at the junction between the small hydrophobic (SH) gene and the hemagglutinin-neuraminidase (HN) gene gave the best immunity against HPAI H5N1 challenge: a dose as low as 1,000 PFU was sufficient to protect against lethal HPAI H5N1 challenge in mice. The work suggests that recombinant PIV5 expressing H5N1 HA has great potential as an HPAI H5N1 vaccine.