Vejen har formentlig fået sit navn, fordi den var den første sidevej til Frederiksberg Allé. Den blev anlagt i 1851.
Den hed oprindeligt Christiansholms Allé efter ejendommen Christiansholm, der lå på hjørnet af Gammel Kongevej. Vejen har også haft navnet Sankt Jørgens Vej. I 1869 fik den sit nuværende navn, som dog i nogle år havde stået på bykortene.
Nyvej var oprindeligt en privat vej, anlagt af de første grundejere, der byggede landsteder langt udenfor byen. Det var ikke bare den landlige idyl, der gjorde Frederiksberg attraktiv, men også at man her undgik smitte, når epidemier ramte byen.
I dag er der både villaer og etagebyggeri på vejen og enkelte af de oprindelige villaer er bevaret. Det gælder f.eks. Nyvej 5, der er opført i 1857.