«Лета 7105 (1597) году Юрье Долгушин усть-цылемец, да литовский полоненик, да Смирной пинежанин лавелец первые Мунгазею проведали Надым реку, а на другой год Таз реку. А воевода первый в Мунгазеи Мирон Шоховской».
Это летописное свидетельство совершенно не соответствует действительности, ибо еще в конце XV века новгородский безымянный книжник писал в сказании «О человецех незнаемых в Восточной стране»: «На Восточной стране, за Югорскую землею над морем живут люди самоеды, зовомые Малгонзеи». Более того, русские промышленники освоили этот район столь основательно, что пушной промысел там стал малоприбыльным. Требовался опорный пункт для дальнейшего освоения Сибири и уничтожения в ней всякого ценного зверя.
Назначенный воеводой в 1600 году Мирон Шаховской отправился из Тобольска на кочах, однако, попав в бурю, потерял все суда. Тогда он продолжил путь по земле, но на Пуре на него напала «пуровская и енисейская самоядь», в результате чего часть стрельцов погибла, а сам Шаховской был ранен. Существует версия, что этой операцией руководили и оплатили ее русские промысловики, не желавшие появления в Мангазейском уезде официальных лиц, которые наверняка стали бы мешать им обворовывать казну. Дальнейшая судьба его отряда долгое время была неизвестна, поэтому первыми воеводами, посланными на выручку Шоховского и построившими Мангазею, считались Василий Масальский и Савлук Пушкин. Однако дендрологический анализ самых ранних венцов срубов показал, что спилены они в 1600 году, а положены весной 1601, то есть до прибытия подмоги. Следовательно, первым воеводой Мангазеи, начавшим строительство острога, был Шоховской, вскоре, вероятно, от ран умерший.
В 1607 году тут уже была крепость, кремль. Тогда же возник и посад.
Царский наказ предписывал новым воеводам пригласить в острог лучших самоедов и сказать им жалованное слово:
«Прежде приходили к ним в Мангазею и Енесею вымичи, пустозерцы и многих государевых городов торговые люди, дань с них воровством брали на себя, а сказывали на государя. Обиды, насильства и продажи от них были им велики, а теперь государь поставил в их земле острог от торговых людей беречь, чтобы они жили в тишине и покое и ясак платили в казну без ослушанья. Велено также было послать служилых людей, переписать самоедов и взять в острог заложников. Сюда же собрать торговых и промышленных людей и объявишь им, чтоб не смели торговать заповедными товарами — панцирями, шеломами, копьями, саблями, топорами, ножами и вином, а другим торговать вольно, платя десятину в казну».
По «Росписному списку 1625 года» город Мангазея снаружи имел такой вид. С приезда — в стене башня Спасская, проезжая, четырехугольная, а под ней двое ворот; башня Успенская, угловая от речки Остеровки; башня Ратиловская, угловая; башня Давыдовская, от реки Таз угловая, четырехугольная, и башня Зубцовская. Городские стены по 1,5 сажени (3,2 метра), вокруг города — 131 сажень (240 метров). Внутри острога находились две церкви — Троицкая и Успенская, — воеводский двор, съезжая изба, таможня, гостинный двор, торговая баня, амбары и лавки, тюрьма и избы населения. Постоянно проживающих в то время было около 100 человек, зато временно — промышленных и торговых — до 1000. «Женок беспутных» и опустившихся ярыжек-пропойц никто не считал.
Всё время между острогом и посадом шла необъявленная война, сменявшиеся воеводы и городские головы не уставали жаловаться друг на друга царю. Например, воевода Жеребцов писал на голову Курдюка Давыдова: «Стрельцы и козаки проигрались зернью донага, а Курдюк де сам скупшичает, дает зерншикам стрельцам и козакам деньги… Говорил ему в розряде, и при служилых людях, и при целовальниках, что он, Курдюк, так делает не гораздо, что служивым людям дает деньги в рост, и служилые люди от него проигрались донага». Наконец, во время воеводства Кокорева и Палицына, который поддержал посад, дело дошло до пушечной пальбы между воеводами.