A mais antiga documentação escrita de Estocolmo data de 1252 d.C. e descreve a cidade como um local de comércio de ferro, mas em algumas sagas nórdicas diz-se que ela é a cidade perdida de Agnafit (onde o lendário Rei Ange foi enforcado pela sua esposa prisioneira Skjalf). Outra estória diz que a cidade foi fundada pelo sueco Birger Jarl para proteger o recém-nascido país das marinhas invasoras. Independentemente de qual (se alguma) está correta, a cidade rapidamente se desenvolveu em um centro de comércio, mineração e pesca, finalmente entrando na Liga Hanseática.
No século XV, um movimento pela independência nacional começou a se formar em Estocolmo, já que o povo da Suécia ansiava derrubar seus governantes dinamarqueses. A revolução não deu certo, infelizmente, e em 1520 o Rei Cristiano II da Dinamarca entrou na cidade e incitou o Banho de sangue de Estocolmo, um massacre da maioria das forças opositoras suecas. Outros protestos por todo país nos anos seguintes tiveram mais sucesso e romperam a União de Kalmar (o agradável nome para o controle dinamarquês da Escandinávia) e a Suécia finalmente ganhou sua independência. O primeiro rei da Suécia, Gustavo Vasa, foi coroado em 1523 e a população de Estocolmo começou a florescer. Em cem anos, a população sextuplicou.
Durante a segunda metade do século XX, Estocolmo se transformou em um dos grandes centros acadêmicos da Europa. A Academia Militar de Karlberg, uma das mais antigas do mundo, foi fundada em 1792; o Instituto Karolinska, uma das escolas de medicina mais prestigiosas da Europa, em 1811; o Instituto Real de Tecnologia, em 1827. A mais antiga de todas, porém, é a Academia Real das Ciências da Suécia, casa do prêmio Nobel, que foi fundada pelo naturalista Carl Linnaeus, em 1739. A cidade continuou a se distanciar de suas raízes da pesca, da mineração e do transporte para se focar em pesquisas de alta tecnologia, fabricação moderna e entregar milhões em dinheiro a cientistas até então obscuros.