В следующем, 1601 году посланы были с тою же целью воеводы князь Василий Масальский и Савлук Пушкин с двумястами воинских людей. Им дан был подробный наказ, начало которого не уцелело, но из оставшейся части которого видно, что они должны были взять с собою из Тобольска, Сургута и Березова «литвы и казаков и стрельцов на обмену перед прежним (т. е. посланными с князем Шаховским) вдвое», также определенное число воинского снаряда и провианта (в том числе четыре пушки), запастись проводниками (вожами) из «зырян торговых людей и вымичей, которые бы ход знали и талмачить умели», и идти на девяти кочах, двух лодках морских да двух дощаниках. Идти им велено было «наспех, днем и ночью, с великим бережением, чтоб им… придти водяным путем до заморозов», а «идучи, разведывать про князя Мирона (Шаховского) и про Данила накрепко», где ныне они, поставлен ли ими острог и т. д., и если острог уже заложен, то сменить в нем ранее посланный отряд, а если нет, то заложить новый, привести к присяге окрестную самоедь, разыскать Мирона Шаховского с товарищами, выручить их, подать им помощь в случае надобности и т. п. Из последующей грамоты 7111 года явствует, что князь Масальский и Савлук Пушкин в Мангазее устроились, но видно также, что город существовал уже до них, а из этого можно заключить, что основание ему было положено еще Шаховским, что подтверждается и свидетельствами сибирских летописей.
Первоначально острог предполагалось поставить на устье реки Таз, но в наказе предоставлено было воеводам право выбрать и другое подходящее место, причем указывалось на промышленные острожки и какой-то «Пантуев городок». Как бы то ни было, но город был заложен по среднему течению Таза, верстах в 200 от его устья, и стал известен под именем Мангазеи. В 1603 году в Мангазею был послан воевода Федор Булгаков, и ему была дана всякая церковная утварь, а также поручено было взять из Березова священника и построить в Мангазее гостиный двор (церковь была построена уже, по-видимому, при князе Масальском). В 1608 году в Мангазею доставлялся уже ясак не только самоедами, жившими по реке Тазу, но и многими из енисейских самоедов и остяков, а равно частью тунгусов по реке Нижней Тунгуске. Тогда же близ устья реки Турухан было построено зимовье, переименованное впоследствии в Новую Мангазею и затем в Туруханск.
От 1616 года сохранилось известие, что архангелогородцы, идя вдоль Мезенских и Пустозерских берегов, через Вайгачский пролив, в Карское море, дошли до реки Мутной (текущей поперек полуострова Ямал), шли по ней 5 дней до озера и, перетащив из него суда волоком в другое озеро, Зеленое, спустились в речку Зеленую и вошли в Обскую губу, а затем, повернув отсюда в Тазовскую губу, пошли вверх по реке Тазу и прибыли в Мангазею, проложив таким образом морской путь из Архангельска до этого города, — путь, торговля по которому была, однако, из-за фискальных целей запрещена в 1620 году.
В 1619 году Мангазея выгорела, и по одному известию (у Щеглова) город тогда же был перенесен в Туруханское зимовье, но по другим, более достоверным свидетельствам, оставление старой Мангазеи последовало много позже, именно не прежде пожара 1642 года.
По словам Миллера, в одной «летописи о мятежах» значится, что город Мангазея был поставлен по приказу царя Бориса, «а ставил город князь Василий Мосальский Рубец», но это известие не подтверждается другими источниками.
По словам Миллера, «в сибирских летописях упоминается, что еще в 7106 году из Москвы отправлен был для проведывания Мангазейской страны некто Федор Дьяков, который с двумя из Тобольска с ним отправленными целовальниками в тамошних местах был и первый там ясак в государеву казну собрал, с чем он в 7108 году в Москву возвратился».