Sjötullsgatan är känd första gången på 1848 års stadskarta.

Gatan löpte österut från Sjötullen – stadens tullgräns mot havet. Stadstull, eller lilla tullen, var en införselavgift som 1622–1810 togs ut på handelsvaror som skulle säljas i staden. Den betalades i Norrköping vid någon av de fyra tullarna: Sjötullen, Norrtull, Södertull och Västertull.