Recombinant vesicular stomatitis viruses (VSV) are excellent candidate vectors for vaccination against human diseases. The neurovirulence of VSV in animal models requires the attenuation of the virus for use in humans. Previous efforts have focused on attenuating virus replication. Studies presented here test an alternative approach for attenuation that uses a matrix (M) protein mutant (rM51R) VSV as a vaccine vector against respiratory infection. This mutant is attenuated for viral virulence by its inability to suppress the innate immune response. The ability of rM51R VSV vectors to protect against lethal respiratory challenge was tested using a vaccinia virus intranasal challenge model. Mice immunized intranasally with rM51R vectors expressing vaccinia virus antigens B5R and L1R were protected against lethal vaccinia virus challenge. A single immunization with the vectors provided protection against vaccinia virus-induced mortality; however, a prime-boost strategy reduced the severity of the vaccinia virus-induced disease progression. Antibody titers measured after the prime and boost were low despite complete protection against lethal challenge. However, immunized animals had higher antibody titers during the challenge, suggesting that memory B-cell responses may be important for the protection. Depletion experiments demonstrated that B cells but not CD8 T cells were involved in the protection mediated by rM51R vaccine vectors that express B5R and L1R. These results demonstrate the potential of M protein mutant VSVs as candidate vaccine vectors against human diseases.