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.