Novirhabdoviruses like the Viral hemorrhagic septicemia virus (VHSV) are rhabdoviruses infecting fish. In the current study, RNA genomes of different VHSV field isolates classified as high, medium or low virulent phenotypes have been sequenced by next-generation sequencing and compared. Various amino acid changes, depending on the VHSV phenotype, have been identified in all the VHSV proteins. As a starting point, we focused our study on the non-virion (NV) non-structural protein in which an arginine residue (R116) is present in all the virulent isolates and replaced by a serine/asparagine residue S/N116 in the attenuated isolates. A recombinant virus derived from a virulent VHSV strain in which the NV R116 residue has been replaced by a serine, rVHSVNVR116S, was generated by reverse genetics and used to infect juvenile trout. We showed that rVHSVNVR116S was highly attenuated and that surviving fish were almost completely protected from a challenge with the wild-type VHSV.