The failure to develop vaccines to protect against important infectious diseases such as human immunodeficiency virus type I (HIV-1) or Hepatitis C virus (HCV) has increased the interest in new vaccine strategies. One of these methods is immunization with an attenuated recombinant viral vector expressing a foreign antigen, which could protect individuals from later exposure to the respective pathogen. A new method to recover a non-segmented negative-stranded RNA virus (NNSV) from cDNA was described for the first time for rabies virus (RV), a member of the rhabdovirus family. The same approach was successfully used for another rhabdovirus, vesicular stomatitis virus (VSV), and opened the possibility to use rhabdoviruses as vaccine vehicles and biomedical tools. Further research showed that the genomes of rhabdoviruses are highly flexible, easy to manipulate, and able to express large and even multiple foreign genes, and therefore are excellent vaccine candidates. In addition, it has been shown for both RV and VSV that their single surface glycoprotein G, which is responsible for attachment and fusion to the host cell, can functionally be replaced by other viral or cellular glycoproteins. This review gives an overview of the use of RV and VSV as promising new candidates in the fight against HIV-1 and other human diseases.