Mange gader på Østerbro har navne efter danske provinsbyer.
Næstvedgade fik sit navn i 1925 og i 1931 blev det endvidere navnet for den del af gaden, der ligger øst for Strandboulevarden. Tidligere hed gaden Livjæger Allé (se nærmere om dette navn under Livjægergade).
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.