The present invention relates to vesicular stomatitis virus (VSV) matrix (M) protein mutants. One mutant M protein includes a glycine changed to a glutamic acid at position (21), a leucine changed to a phenylalanine at position (111) and a methionine changed to an arginine at position (51). Another M protein mutant includes a glycine changed to a glutamic acid at position (22) and a methionine changed to an arginine at positions (48) and (51). Yet another VSV M protein mutant includes a glycine changed to a glutamic acid at position (22), a leucine changed to a phenylalanine at position (110) and a methionine changed to an arginine at positions (48) and (51). The present invention is directed also to recombinant VSVs (rVSV) having these M mutants and to vaccines based on the rVSV having the M mutants of the present invention. These new rVSVs having the mutant M were significantly attenuated and lost virulence, including neurovirulence, and are capable of inducing an immune responses against an antigen of interest. In addition, a rVSV serotype Indiana having the first described M mutant is capable of efficient replication at 31° C., and of poor replication or incapable of replication at about 37° C. or higher.