В сагах Снорри Стурлусона говорится, что Осло был основан конунгом Харальдом III Суровым (1015–1066), и, после того как историк Петер Андреас Мунк (1810–1863) уточнил ещё и дату – 1048 г., – именно этот год и стал считаться днём рождения города. Однако недавние археологические раскопки показали, что христианское поселение существовало здесь до начала XI в., что сделало возможным отметить тысячелетие Осло в 2000 г. – всего через 50 лет после 900-летнего юбилея! Надо сказать, это в какой-то степени соответствует рассказам Снорри: по его словам, город был основан в том месте, где земля была плодородной, население было большим, где выросло торжище и откуда всю страну можно было защитить от набегов датчан (или же самим совершать походы на Данию).

Первоначально центр города находился в устье реки Алны – сейчас этот район называется Старым городом (Gamlebyen).

Археологические раскопки, проведённые во второй половине XX в., показали, что около 1000 г. в Осло уже существовала церковь, названная в честь святого Клементия. Более того, одновременно с «официальным» основанием города спустя полвека Харальд Суровый повелел также заложить здесь ещё одну церковь – Святой Марии. Ныне её руины можно увидеть у железнодорожной станции Лоенга.

В 1070 г. король Олаф III Тихий (1050–1093) провозгласил Осло епископством и, тем самым, религиозным центром всего региона. Покровителем был объявлен святой Хальвард, и в его честь на центральной площади был возведён собор в самом начале XII в. Спустя полвека в городе появились монастырь и кафедральная школа.

Церкви и монастыри были в то время крупными землевладельцами, а потому во многом определяли экономическую жизнь города. Обнаруженная при раскопках широкая сеть дорог, улиц и фундаментов домов указывает на то, что в те времена в городе проживало 3000–4000 человек.

Основателем столичного собора был Сигурд I Крестоносец (1090–1130) – первый норвежский король, поселившийся в Осло, где он позднее скончался и был похоронен. К моменту его смерти основные части собора, начатого в 1100-х гг., уже были готовы, и вскоре сюда перевезли также мощи святого Хальварда, обретшего своё последнее пристанище у алтаря.

Святой Хальвард изображён на печати Осло (столица Норвегии наравне с Бергеном и Тёнсбергом не имеет отдельного герба): святой представлен с неизменными атрибутами – тремя стрелами, которыми он был убит, и мельничным камнем, что позже привязали к его шее, дабы его утопить, – а у его ног лежит мёртвая женщина. За Хальвардом видны львы (это было довольно типично для древних норвежских изображений), и он восседает на троне, что приравнивает его к королям.

Женщина стала единственным отличием современного герба от древнейшей печати города, где на её месте лежал вооружённый боец – один из тех, кто убил Хальварда, в итоге одержавшего победу над злом. Поскольку древняя печать была в плохом состоянии, воина приняли за женщину, которую святой хотел защитить.

В своём первоначальном виде герб просуществовал почти 3 столетия, изменяясь лишь незначительно. Однако к XVII в. церковь Святого Хальварда превратилась в руины – да и легенду начали подзабывать. Так в 1659 г. появилась новая печать Осло, в общих чертах сохранявшая прежний дизайн – однако святого заменили женской фигурой, у чьих ног покоился павший рыцарь. Мельничный камень стал тоньше и теперь скорее походил на кольцо. Такая интерпретация получила невероятную популярность в Дании в XVIII в., где дама была принята за королеву Маргарету, объединившую Швецию, Норвегию и Данию в прочный союз (что весьма символично передавалось тремя стрелами и кольцом), ну а павший рыцарь символизировал не кого иного, как её побеждённого соперника Альбректа Мекленбургского.