La primera mención escrita a Estocolmo se remonta al año 1252 d. C., donde se describe como una ciudad en la que se comerciaba con hierro. Sin embargo, en algunas sagas nórdicas se sostiene que es la ciudad perdida de Agnafit (donde el legendario rey Agni fue ahorcado por Skjalf, su prometida cautiva). Otra historia asevera que la ciudad la fundó el jarl sueco Birger (o "Birger Jarl") para proteger al incipiente país de las armadas invasoras. Sea cual sea la verdadera historia, lo cierto es que el lugar se convirtió rápidamente en un centro comercial, minero y pesquero que llegó a formar parte de la Liga Hanseática.
En el siglo XV, comenzó en la ciudad un movimiento de independencia nacional cuando el pueblo sueco aspiró a derrocar a sus gobernantes daneses. Por desgracia, la revolución fracasó y, en 1520, el rey danés Cristián II entró en la ciudad y propició la "masacre de Estocolmo", una terrible matanza de las fuerzas de oposición suecas. Los levantamientos que se sucedieron en el país durante los años siguientes tuvieron más éxito y disolvieron la Unión de Kalmar (el nombre "bonito" para designar el control de Escandinavia por parte de Dinamarca), y los suecos consiguieron la independencia. El primer rey de Suecia, Gustavo Vasa, fue coronado en 1523, y la población de Estocolmo empezó a crecer rápidamente. En un centenar de años, los habitantes de la ciudad se multiplicaron por seis.
Durante la segunda mitad del siglo XX, Estocolmo se convirtió en uno de los grandes centros del aprendizaje de Europa. La Academia Militar de Karlberg, una de las más antiguas del mundo, se fundó en 1792. En 1811 abrió sus puertas el Karolinska Institutet, una de las facultades de medicina más prestigiosas de Europa, y en 1827 lo hizo el Instituto Real de Tecnología. Más antigua todavía es la Real Academia de las Ciencias de Suecia, sede de los Premios Nobel, fundada en 1739 por el naturalista Carlos Linneo. La ciudad ha ido abandonando sus raíces pesqueras y mineras para convertirse en uno de los principales centros de la investigación científica.