A svéd vikingek fővárosa a Mälaren-tó Björkö szigetén fekvő Birka városa volt. Stockholm helyén pörköltből kikandikáló húsdarabok gyanánt álltak ki a sziklás szigetek a mainál legalább öt méterrel magasabb szintű vízből. A szárazföld folyamatosan kiemelkedett a tengerből, és a Mälaren-tó déli kijárata a Keleti-tengerre a 800-as évek közepe táján használhatatlanná vált. A lübecki kereskedők hajói azontúl csak kelet felől közelíthették meg Birkát és a Mälaren-tó partján fekvő településeket. A Mälaren-tó és a Keleti-tenger találkozásánál, a stockholmi Óváros helyén lakatlan, sziklás sziget állta útjukat. A sekély szoroson - Strömmenen - nem tudtak felhatolni, ezért a sziget keleti partjára kirakodott árut átcipelték a nyugati oldalon várakozó "Mälar-járó" hajókra, és onnan folytatták az utat. A körülményes közlekedés miatt nehezen megközelíthető Birka elnéptelenedett. A kereskedelem központja előbb a Mälaren északi partján fekvő Sigtunába, majd 1187-ben, az észtek pusztítása után, az előnyösebb stratégiai helyzetű Stockholmba költözött.

A monda - és Johannes Messenius, középkori történész-püspök - szerint a svédek Sigtuna pusztulása után a Mälaren vizébe vetett, arannyal és ezüsttel tömött tölgyfa tönkre bízták az új főváros helyét. Amint az várható volt, az áramlat Stockholm szigetén sodorta partra a rönköt. Selma Lagerlöf Nils Holgersson csodálatos utazásában a sziget szépségével indokolja a választást. A lakatlan szigeten megpihenő halász legnagyobb meglepetésére, a sziklákon addig lustán heverő fókák bőrüket levetve gyönyörű leányokká változtak, és kecses táncot lejtettek a holdfényben. A halász az egyik fókabőrt gondosan eldugta egy nagy kő alá, és a bőrgúnyáját sírva kereső szépséges leányzót hazavitte a szülői házba. A jó bánásmód következtében az ex-fóka egyre jobb kedvre derült. Amikor a halász megkérte a kezét, boldogan igent mondott. Csónakba szálltak, és elindultak papot keresni. Stockholm szigetéhez érve a halász felidézte ismerkedésük történetét. A hitetlenkedő menyasszony kérésére kikötött, és előkereste a bizonyítékot. A menyasszony magára kapta a bőrt, és egy ugrással a vízben termett. A pórul járt vőlegény elkeseredésében utána hajította a szigonyát. A haldokló fóka vére bearanyozta a szigetet, a kopár szirteket virágok lepték el. Halászok és kereskedők telepedtek le a szigeten, míg egy szép napon maga a király is odaköltöztette a székhelyét...

Stockholm neve először Birger Jarl királyi helytartónak a lübecki kereskedőknek adó- és vámmentességet szavatoló okiratán szerepel. Birger Jarl 1250 táján építtetett Tre Kronor (Három Korona) várával a "Mälaren zárjává" tette Stockholmot. A tengeren garázdálkodó kalózhajók felhatolásának megakadályozása, és a hajóforgalom ellenőrzése céljából sorompóval nyitható cölöpkoszorút vertek a szigetet körülvevő víz medrébe. Innen eredhet a Stockholm név is: A stock cölöpöt, oszlopot, a holme pedig szigetecskét jelent. (Mások szerint a Södermanland és Uppland országrészek határát jelölő cölöpsornak köszönheti a nevét.)

Stockholm darázsderékszerűen kötötte össze Észak- és Dél-Svédországot. Az egykori várfal a mai Prästgatan és Baggensgatan utcák mentén húzódott. A városba északról és délről rövid hidakon, két, toronnyal ellátott kapun: a Norreporton - a mai Mynttorget helyén - és a Söderporton - a mai Slussennél - keresztül lehetett bejutni. A szomszédos Riddarholmen szigetén szélmalmok, és kolostor, míg az északi Helgeandholmen szigetén kórház állt. Samuel Kiechel, német kereskedő 1586-ból származó útinaplójában cölöpökre épült házakról, lassú és körülményes szárazföldi közlekedésről számolt be. A város keskeny és gödrös utcái minden tervszerűség nélkül kanyarogtak, az emberek és háziállataik ürülékkel kevert sárban caplattak. Még a nemesi lakások falai is vakolatlanok voltak, az asztal fölött kifeszített vászon a plafonon mászkáló pókokat akadályozta meg abban, hogy beleessenek az ételbe. (Ez utóbbit nem tartotta említésre méltónak.)

A középkorban a várfalakon kívül eső épületeket ostrom idején lerombolták, ezért aránylag későn alakultak ki a külvárosok, később népesültek be a szomszédos szigetek. Az első külváros Norrmalm (Északi városrész), majd a déli Åsön, mai nevén Södermalm, a legújabb pedig a keleti, előkelő Östermalm, amelyet a XV. századtól 1885-ig itt működő királyi istállóról Ladugårdlandet-nek azaz istálló-tájnak (vagy vidéknek) hívtak. (A "malm" szó homokos talajt, környezetéből kissé kimagasló területet, szóösszetételekben pedig kisebb külvárost jelent.)

Stockholm a Kalmári-unió megszűnte után, Gusztáv Vasa uralkodása alatt lett a svéd birodalom adminisztratív központja, de csak az 1600-as években, II. Gusztáv Adolf és leánya, Krisztina királynő uralkodása alatt vált igazi fővárossá. A partokat feltöltötték a Strömmen fölé magasló Brunkeberg-hegy lebontásából származó kaviccsal, utcákat építettek a várfalakon kívül. 1630-ban elkészült az első városterv, a tűzveszélyes faházak helyére kőépületeket emeltek, a gerendázatot felújították, a homlokzatokat a családi címert ábrázoló, cifrára kovácsolt, vas keresztvasakkal és az építés évszámával díszítették. Az 1700-as években szövödék, textilmanufaktúrák, dohánygyárak, üveg- és porcelángyárak működtek a részben a szigetekre, részben pedig a Mälaren-tó és a Keleti-tenger partjaira épült Stockholmban. Az 1800-as évek közepére Stockholm ipari város, a Skeppsholmenen hajókat építettek, Liljeholmenen sztearingyár működött, a Kungsholmenen megalakult a Bolinder mechanikai műhelyek és az L.M. Ericsson. Számos sörfőzde elégítette ki a lakosság növekvő igényeit. (100 lakosra jutott egy kocsma.) A szárazföldi és légi közlekedés rohamos fejlődésével megszűnt az elszigeteltség. "Észak Velencéje" ma már nem a világ legnagyobb kisvárosa, hanem a szolgáltató ipar, a pénzpiac, és a információs technológia központja.