最早描述斯德哥爾摩的書面文件可追溯到1252年，書中將這個城市描述成鐵礦貿易之城，但在一些關於挪威傳說的書本裡，這座城市被稱為昂熱非特的失落之城（據說，被昂熱國王俘虜的新娘斯凱加弗將國王絞死了)。根據另一個傳說，這個城市是由瑞典人比爾格•雅爾建立的，目的是讓這個羽翼未豐的國家免遭海軍入侵。不管哪個版本是真實的（或者都是假的），這個城市迅速發展成商業、礦業和漁業的中心…最後加入了漢薩同盟。

15世紀時，因為瑞典人渴望推翻丹麥的統治，所以民族獨立運動開始出現在斯德哥爾摩。不幸的是革命並不順利，1520年，丹麥國王克里斯蒂安二世來到這個城市，在他的煽動下，斯德哥爾摩慘案發生，這是一場針對瑞典大部分反對勢力的大屠殺。接下來幾年間，全國的起義活動獲得了越來越多的成功，並且從卡爾馬聯盟（這是丹麥為控制斯堪地那維亞半島而取的一個好聽的名字）脫離了出來，瑞典最終獲得獨立。瑞典第一任國王古斯塔夫•瓦薩在1523年登基，瑞典人口也開始急劇增長。在一百年間，公民數量增加了六倍。

在20世紀下半葉，斯德哥爾摩成為了歐洲偉大的學術中心之一。凱伯爾軍校成立於1792年，是世界上最古老的軍校之一；卡羅林斯卡學院成立於1811年，是歐洲最負盛名的醫學院之一；此外還有成立於1827年的瑞典皇家理工學院。其中最古老的是瑞典皇家科學院，它是諾貝爾獎的發源地，由著名的自然學家卡爾•林奈在1739年創立。這個城市逐漸將發展的重點由之前的漁業、礦業和船舶業轉向高科技研究、現代製造業，並且為那些不出名的科學家投資數百萬用於他們的科學研究事業。