The active template for RNA synthesis for vesicular stomatitis virus (VSV) and other negative-strand viruses is the RNA genome in association with the nucleocapsid (N) protein. The N protein molecules sequester the genomic RNA and are linked together by a network of noncovalent interactions. We previously demonstrated that mutations predicted to weaken interactions between adjacent N protein molecules altered the levels of RNA synthesis directed from subgenomic ribonucleoprotein (RNP) templates. To determine if these mutations affect virus replication, recombinant viruses containing single-amino-acid substitutions in the N protein were recovered. Four mutations altered transcription and genome replication levels, perturbed viral protein synthesis, and inhibited virus replication. Selective pressure for improved virus replication was applied by eight sequential passages. After five passages, virus replication improved and RNA synthesis recovered concomitantly with the restoration of the protein molar ratios to near-wild-type levels. Genome sequences were compared before and after passage to determine whether compensatory mutations were selected and to potentially identify interactions between N protein molecules or between the RNP template and the viral polymerase. Improved virus replication correlated with the selection of additional mutations located in cis-acting transcriptional regulatory sequences at the gene junctions of the genome rather than in coding sequences, with one exception. The engineered N gene mutations perturbed mRNA and protein expression levels, but the selection of modified transcriptional regulatory sequences with passage facilitated the restoration of wild-type protein expression by modulating transcription levels, reflecting the adaptability and versatility of gene regulation by transcriptional control.