Es gibt keine historischen Belege für eine Existenz Stockholms vor der Mitte des 13. Jahrhunderts. Eventuell gab es jedoch ältere Verteidigungsanlagen zur Sicherung der Einfahrt in den Mälarsee. Eine Besiedlung kann jedoch nicht nachgewiesen werden.
Der Ort, wo heute Stockholm steht, wird zum ersten Mal vom isländischen Dichter und Sagenschreiber Snorre Sturlasson (1178-1241) erwähnt: Er beschreibt eine Pfahlbarriere über die heutige Wasserstraße Norrström, die er Stocksundet nannte. Bei Ausgrabungen in den späten 1970er Jahren kamen tatsächlich Überreste von Wasserpfählen zum Vorschein, die aus dem 11. Jahrhundert stammen. Außerdem wird von Snorre auch ein Befestigungsturm aus dem 12. Jahrhundert erwähnt, der an genau der Stelle gestanden haben soll, an der heute das königliche Schloss steht.
In historischen Dokumenten (in der mittelalterlichen Erik-Chronik) ist von Stockholm erstmals 1252 die Rede, dort steht, dass der Gründer Stockholms, der Regent Birger Jarl, um das Jahr 1250 eine Festung bauen wollte, um den Mälarsee vor Piratenplünderungen zu schützen.
Unter der Regierung Birger Magnussons und des Königs Magnus Ladulås entwickelte sich Stockholm in den folgenden Jahrzehnten zu einer wichtigen Handelsstadt, was vor allem durch Verträge mit der Hansestadt Lübeck gefördert wurde. Die Hanse kontrollierte den schwedischen Überseehandel vom 13. bis ins 17. Jahrhundert. Um 1270 wurde Stockholm in Dokumenten als Stadt bezeichnet und, obwohl Stockholm nicht wie viele schwedische Städte schon Anfang des 13. Jahrhunderts entstand, wurde es 1289 in einem Dokument als die bevölkerungsreichste Stadt des Königreiches beschrieben. Die ersten gesicherten Annahmen zur Größe der Stadt beziehen sich auf die Mitte des 15. Jahrhunderts, als Stockholm etwa 1.000 Haushalte, also ungefähr 5.000 bis 6.000 Einwohner hatte. Aus demselben Jahrhundert (1436) stammt auch der erste Privilegienbrief. Trotz seiner Größe und günstigen Lage war Stockholm noch nicht die Hauptstadt, denn der König, wie auch sein Sohn, Magnus Ladulås, hatten noch keinen festen Regierungssitz.
Der hauptsächliche Grund für die rasche Entwicklung der Stadt war ihre strategische Lage. Stockholm beherrschte die Zufahrt zum Mälarsee, der seinerseits eine aufgrund der Landwirtschaft und Eisenherstellung wirtschaftlich wichtige Region erschloss. Die Ausdehnung der Stadt war zu dieser Zeit auf die Insel Stadsholmen (heute Gamla Stan) beschränkt. Die Insel selbst war um ein Drittel kleiner als heute, und die Ströme wesentlich weiter.