Codon pair bias (CPB), which has been observed in all organisms, is a neglected genomic phenomenon that affects gene expression. CPB results from synonymous codons that are paired more or less frequently in ORFeomes regardless of codon bias. The effect of an individual codon pair change is usually small, but when it is amplified by large-scale genome recoding, strikingly altered biological phenotypes are observed. The utility of codon pair bias in the development of live attenuated vaccines was recently demonstrated by recodings of poliovirus (a positive-strand RNA virus) and influenza virus (a negative-strand segmented RNA virus). Here, the L gene of vesicular stomatitis virus (VSV), a nonsegmented negative-sense RNA virus, was partially recoded based on codon pair bias. Totals of 858 and 623 silent mutations were introduced into a 5=-terminal segment of the viral L gene (designated L1) to create sequences containing either overrepresented or underrepresented codon pairs, designated L1sdmax and L1min, respectively. Analysis revealed that recombinant VSV containing the L1min sequence could not be recovered, whereas the virus with the sdmax sequence showed a modest level of attenuation in cell culture. More strikingly, in mice the L1sdmax virus was almost as immunogenic as the parental strain but highly attenuated. Taken together, these results open a new road to attain a balance between VSV virulence and immunogenicity, which could serve as an example for the attenuation of other negative-strand, nonsegmented RNA viruses.