Gaden er opkaldt efter borgmester Jens Christian Juel Gammeltoft (1818-1873). Han blev valgt til borgerrepræsentationen i 1856 og var fra 1860 borgmester. Han havde bl.a. ansvaret for kommunens hospitalsvæsen i den periode, hvor Kommunehospitalet blev bygget.

Bebyggelsen i Gammeltoftsgade er opført i årene fra 1870 og frem, efter af voldanlægget omkring København blev nedlagt.

Langs Gammeltoftsgade lå fra 1600-tallet en kanal, der forbandt Sortedamssøen med Stadsgraven, altså voldgraven foran Københavns befæstning. Renden blev også brugt til drikkevandsforsyning, og i 1700-tallet udført som en overdækket tunnel. Anlægget af tunnellen blev ledet af militærarkitekten Heinrich Ernst Peymann, og den fik derfor navnet Peymanns Rende.