Den 18 september 1958 namngavs Fleminggatan i Gamla staden.

På platsen för nuvarande Hedvigs kyrka låg 1582–1604 renässansslottet Norrköpingshus, ritat av Hans Fleming och uppfört under hans ledning. Fleming (ca 1545–1623), nederländsk skulptör och byggmästare, bodde under många år i Norrköping. Han tillhörde tidens ledande arkitekter och ritade bland annat också Johannisborg.

Gatan hette tidigare Södra Strömsgatan (från 1769).