Gatan löper intill Sjötullen, som var 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.

Åren 1915-1958 hette gatan Södra Strandgatan. På 1800-talet fanns en äldre Sjötullsgatan strax norr om den nuvarande.