Hollingsted nævnes første gang 1153 som Hugstaeth, 1285 som Huglaestath.
Hollingsted var i vikingetiden handelsplads på vejen mellem Hedeby og Nordsøen. Formodentlig sejlede skibene ad Ejderen og Trenen op til Hollingsted, hvorefter varerne er blevet omladet og ført over land til Hedeby.
Ifølge en teori har der været en kanal mellem Trenen og Slien, som løb langs volden Kovirke. Ad denne kunne vikingetidens fartøjer måske transporteres mellem Hedeby og Hollingsted. I 849 skal missionæren Ansgar være landsteget her.[kilde mangler] Han byggede senere den første danske kirke i Hedeby.
Hollingsted markerer også den vestlige ende af Dannevirke. Dannevirkes del ved Hollingsted kaldes for Krumvold og har kun få synlige levn. Byens museum hedder Hollinghuus.