Mange gader på Østerbro har navne efter danske provinsbyer.
Næstvedgade fik sit nuværende navn i 1925, og i 1931 blev det endvidere navnet for den del af gaden, der ligger øst for Strandboulevarden.
Gaden er dog ældre, og hed tidligere Livjæger Allé (se nærmere om dette navn i artiklen om Livjægergade).
Den blev anlagt omkring 1890, af A. C. Lipke og L. H. Hinrichsen.
Gadeanlægget var en betingelse for, at de fik tilladelse til at udstykke deres grunde, der bl.a blev til Lipkesgade. Langs Livjægergade blev anlagt en grøft, der ledte vandet fra Sortedamssøen ud i Øresund.
Mellem Næstvedgade og Jens Munk Gade blev der i 1938 opført et boligkompleks med tre længer med lejligheder i fem etager. Komplekset blev tegnet af arkitekterne Axel Sørensen og Karl Larsen.