Historia miasta sięga wieku XIII i wiąże się nierozerwalnie z najstarszą dzielnicą Sztokholmu - Gambla Stan, czyli Starym Miastem. Począwszy od pradawnych czasów średniowiecznych, aż do dziś teren ten odgrywał znaczącą rolę. Pierwotnie był strategicznym punktem wykorzystywanym przez rybaków i myśliwych (leży przy śluzie łączącej Morze Bałtyckie z potężnym Jeziorem Mälaren, stanowiącym drogę żeglugową do Szwecji Środkowej). Następnie stał się apetycznym kąskiem dla zaradnych i gospodarnych kupców z Lubeki. To właśnie Niemcy na początku tego stulecia zorganizowali w mieście bazę będącą ośrodkiem rzemiosła i handlu. Dokładna data założenia miasta jest kwestią sporną. Wg tzw. "Kronik z Visby" ("Visbyannalerna") miasto Stockholm założone zostało w roku 1187 przez króla Knuta Erikssona. Natomiast w spisanej później przez innych zakonników "Kronice Erika" ("Erikskrönikan" z roku 1480) stwierdza się, że jarl Szwecji Birger wzniósł na tym terenie Starego Miasta twierdzę Tre Kronor (Trzy Korony). Pamięć o nieistniejącej już twierdzy jest starannie kultywowana. Na jej miejscu wznosi się dziś Pałac Królewski, a trzy korony są symbolem Szwecji znanym w całej Europie. W związku z tym częściej spotykaną datą założenia miasta jest rok 1252.

Pod koniec XIII wieku miasto rozwijało się bardzo prężnie. Było jednym z miast należących do Związku Hanzeatyckiego. Mimo, iż Sztokholm był stosunkowo małym miastem (ok. 7000 mieszkańców), czerpał ogromne korzyści z handlu stając się najważniejszym szwedzkim miastem.

Wiek XIV w historii tego regionu wiąże się z unią kalmarską, która była paktem łączącym kraje skandynawskie osobą jednego monarchy. Unia ta na przestrzeni dziejów oznaczała dla Sztokholmu i całego kraju dominację Duńczyków w efekcie zakończoną słynną sztokholmską krwawą łaźnią, w której wymordowano przeciwników króla. Wydarzenia te z roku 1520 były przyczyną, dla której wyniesiono na tron Gustawa I Wazę - króla reformatora który rozpoczął nową epokę w historii miasta i całego kraju.