Gaden ligger i et kvarter, hvor mange gader er opkaldt efter danske provinsbyer.
Vejen blev anlagt allerede i 1850’erne, og hed oprindeligt Øresundsgade. Navnet blev i 1948 ændret til Vordingborggade på grund af risikoen for forveksling med Øresundsvej på Amager.
I 1800-tallet var der på sydsiden af gaden en blanding af villaer og småindustri.
I Vordingborggade 12-14 lå A/S Georg E. Mathiasen, der fremstillede vaskerimaskiner til f.eks. sygehuse. Virksomheden blev grundlagt i 1903 og lavede i starten bl.a. knallertmotorer. Bygningerne er i dag afløst af et nybyggeri.
Omkring Halsskovgade lå Rønning & Gjerulffs fabrik for kontorartikler, bl.a. blæk.
Bygningen på hjørnet af Vordingborggade og Randersgade blev opført 1917 som teknisk skole med Jesper Tvede (1879-1934) som arkitekt. Fra 1939 til 1954 var den i brug som vandrerhjem.
På hjørnet af Assensgade ligger en ejendom (herover) med en bemærkelsesværdig udsmykning af facaden.
Vordingborggade er ført under jernbanedæmningen og har udkørsel til Kalkbrænderihavnsgade.