Более достоверные источники, нежели камни и могильники, то есть исторические документы, впервые упоминают шведскую столицу лишь в 1252 г. Именно тогда, согласно летописцам, регент Швеции Биргер Ярл укрепил существовавшее на Балтийском море поселение с названием Стокгольм и даровал ему право быть городом, то есть «местом, живущим торговлей и ремеслом и обладающим собственными органами самоуправления, законами и правосудием». Основание города (что предполагало возведение укрепительных сооружений) именно в этом месте было необходимо в целях обороны страны.

Основными обидчиками шведов в эпоху раннего Средневековья были их соседи по Балтийскому морю – эсты (современные эстонцы). Согласно одной из легенд, именно эсты захватили и сожгли небольшой по сегодняшним меркам городок Сигтуну, считавшийся столицей свейского государства. Жителям города, правда, удалось спасти немалую часть своего имущества, которую было решено спрятать в дубовое бревно с выдолбленной сердцевиной и спустить затем на воду, словно корабль. Сигтунцы договорились следовать за бревном до тех пор, пока течение не выбросит его на берег. Это, по их мнению, было бы «знаком свыше» – сам Бог указывал им место, где следовало основать новую столицу. Волны прибили бревно к небольшому островку, известному сегодня как сердце Стокгольма – Старый город. «Выбранный» сигтунскими «сокровищами» островок подходил как нельзя лучше: он располагался в стратегически удобном как для торговли, так и для обороны месте – на слиянии озера Меларен с Балтийским морем. Имя новой столице дали соответствующее – Стокгольм, что прекрасно согласуется с этой столь романтичной легендой: «stock» в переводе со шведского означает «бревно», «holme» – «остров».

Вскоре город превратился в важнейший торговый пункт во всем Балтийском регионе, а власть в нем была поделена между шведами и ганзейцами – немцы составляли почти четверть населения шведской столицы.

После заключения Кальмарской унии управление страной не раз оказывалось в руках датчан, что вызывало недовольство многих обеспеченных шведов, и в 1471 г. дворянство под предводительством Стена Стуре-старшего (ок. 1440–1503, регент Швеции в 1470–1497 гг. и в 1501–1503 гг.) попыталось восстать против датского короля Кристиана I и его сторонников. Решающей стала битва при Брункеберге в Стокгольме, которую выиграли шведы, в результате чего к ним и перешли вся власть и контроль над торговлей в Балтийском регионе. Правда, в 1520 г. другой датский монарх, Кристиан II (1481–1559, король Швеции в 1520–1521 гг.), вторгся в город с целью добиться признания его королем трех стран, на что капитулировавшая местная знать согласилась. Под предлогом празднования этого события Кристиан пригласил самых влиятельных людей Стокгольма, надеявшихся на уступки и примирение, в замок Тре крунур, где был устроен торжественный банкет. На третий день городские ворота заперли, и все противники режима нового короля – священники, дворяне, зажиточные бюргеры – были обезглавлены на центральной площади Стурторьйет (Stortorget). Это событие получило название Стокгольмской кровавой бани. Сын одного из казненных граждан, Густав Ваза, возглавил восстание против Кристиана II и в 1523 г. был провозглашен королем Швеции.

С этого времени начинается развитие Стокгольма как будущей столицы Шведского королевства, хотя официально городу был присвоен этот статус лишь в 1634 г.

Постепенно Стокгольм превратился в процветающий град, пришедший, однако, в упадок в начале XVIII в. из-за бесконечных войн Карла XII, приведших к финансовым трудностям, голоду и чуме, которые унесли жизни каждого третьего жителя столицы.