За Обдорском, последним на пути русским острогом, коломенки и кочи вошли в Обскую губу. Кормщики, которых наняли в Березове, вели суда вдоль левого болотистого берега. До Пантуева — остяцкого городка добрались благополучно, но дальше дела пошли хуже: задули господствующие здесь в августе сильные северные ветры. Северным ветром прижало кочи к берегу так, что идти дальше было нельзя. А чтобы удержаться на месте, бросили якоря, льдины отгоняли баграми. Сгрузили на берег товары и вооружение. Тем временем погода совсем испортилась.

В губу пришли большие льды и со всех сторон окружили суда. Три из них захватило льдами и погнало в море. Оставшиеся суда ждала та же участь. Положение создалось трудное и опасное. Немедленно выслал Мирон Шаховской казака в Березов и просил тамошних воевод прислать ему на помощь оленьи упряжки остяков и самоедов. Но пока казак пробирался по тундре, грянули морозы. В ожидании помощи стали лагерем. В октябре прибыли остяки и самоеды. Было их много — раза в три больше воеводского отряда. Поначалу князцы вели себя мирно и согласились везти русских в Мангазею.

До реки Пур шли они хорошо, и олени их не устали. А вот дальше стали своими юртами и не двигались. Послал Шаховской сына боярского «с разговором» к главному остяцкому князцу, но тот сказал парламентеру, коверкая русскую речь: «Не гоже князю в Мангазею итти, плохо будет да и дороги они туда не ведуют». Тогда князь приказал схватить нескольких зачинщиков и привести к себе, но этим только ухудшил отношения. Собрались остяки и решили идти на русских и силой освободить задержанных. В тундре разгорелся бой. Вооруженные луками восставшие окружили лагерь стрельцов и казаков. Раздались выстрелы, и полетели стрелы. Многие служилые были ранены, а некоторые убиты. Самого воеводу ранили в плечо. С большим трудом удалось оторваться от наступающих и отбить несколько нарт, груженных огнестрельным оружием, но этим дело не поправили. Восставшие угнали ездовых оленей, оставив мангазейских воевод без транспорта. Время было холодное, надвигалась осень. Шаховской приказал продолжать поход. В январе, терпя голод и холод, войско достигло реки Таз. Начались лютые морозы. Снег толстым слоем покрыл тундру и лед. Продвигались вдоль реки медленно. Вначале шла небольшая группа в дозор, и уж потом шли остальные.

По пути встретили несколько заброшенных землянок и избушек и даже один небольшой «самоедский городок», но все пустые. За два месяца воеводы преодолели 300 верст — дошли до мест, где тундра покрыта редколесьем, да и низкий правый берег реки стал выше. В лесу росли лиственница, береза и ель. Место по всему было хорошее. И не сразу заметили, что совсем рядом засыпан снегом городок поморов-звероловов — несколько избушек, землянок и амбаров. На соседней речке стояли их суда. Но в городке никто не жил, знать, все его жители ушли на промысел. Здесь и решили стать лагерем. Стрельцы и казаки заняли землянки и полуземлянки, а воеводы, тобольский сын боярский и атаманы поместились в большой просторной избе, что стояла на самом возвышенном месте. Осмотревшись, они увидели, что промышленные люди выбрали для своего городка удобное место: с севера и юга его окружали речки Ратиловка и Осетровка (Мангазейка), а с запада обрывистый берег вплотную подходил к реке Таз.

Весной выяснились и другие важные особенности городка. К востоку от него лежали озера и болотистая тундра, откуда ни пройти, ни проехать нельзя. Таким образом, со стороны реки и тундры острог был бы защищен от опасности. Придумать лучшее место для «государева острога», казалось, было невозможно. К тому же отыскался и близкий переход с реки Таз на Енисей. Верстах в 200 от лагеря впадала в Таз речка Волочанка (Худосея). По ней добирались до другой реки Волочанки, впадающей в реку Турухан, несущую свои воды в Енисей.

В марте соболиные промыслы закончились. Соболь полинял, порыжел, шкурка его уже не годилась. В апреле к городку из тундры и лесов стали стекаться промышленные люди. Шаховской приказал выбрать среди них доверенного человека в целовальники — таможенные чиновники, чтобы собрать государю десятый соболь. Каждому, уплатившему десятый соболь, целовальники выдавали проезжую грамоту — разрешение на поездку на Русь. К маю пришли к своим кочам и остальные торговые и промышленные люди. Скопилось их довольно много, и все родом из Поморья: пустозерцы, мезенцы, пинежане, кеврольцы, холмогорцы.

Расспросили их мангазейские воеводы о городке и о промыслах и решили рубить тут острог. Всех торговых и промышленных людей направили в лес возить бревна. Более опытные из них строили воеводский двор и съезжую избу. Но самое главное: следовало со всех сторон укрепить «государевы службы». В конце июня, когда оттаяла земля, копали ямы вокруг острога и ставили в них торцом крепкие и толстые еловые и лиственничные бревна. Получилась сплошная стена, только с правой проезжей стороны стрельцы срубили башню и ворота, установили караул.

Еще только закладывался Мангазейский острог; стук топоров и жужжание пил привлекли к нему самоедов и остяков — коренных жителей края. Многие из них никогда не видели бородатых мужиков, дивились их одежде. Воеводы приказали взять среди них старших и привести в съезжую избу, где толмач объяснил им, что надлежит платить ежегодно ясак великому государю.

Летом послал Мирон Шаховской из нового острога в Березов гонца. Но тот запоздал. Весной, не получив вестей от мангазейских воевод и ничего не зная об их судьбе, Федор Шереметьев, по царскому указу, подготовил на Иртыше новую большую экспедицию в Мангазею. Во главе ее стали его родственник князь Василий Мосальский и письменный голова Савлук Пушкин. Для плавания по Оби, Обским и Тазовским губам на верхотурских плотбищах снова строили кочи, морские лодки и дощаники. Из Перми и Вологды привезли якоря, канаты, холсты на паруса. Мосальский и Пушкин получили вдвое больше стрельцов и казаков. В Тобольске им дали 100 да в Березове и Сургуте еще 100 служилых людей. На Мангазею поднималось большое царское войско, чтобы, по мысли тобольского воеводы, разом покончить с «шатостью» остяков и самоедов и привести их в «вечное холопство» московскому царю. Новым мангазейским воеводам на служилых тобольских людей выдали скорострельную пищаль и к ней 200 ядер. Для управления «огненным боем» на воеводском коче ехал пушкарь. В Мангазею пошли три затинные пищали и 200 ядер, 20 пудов зелья-пороха и 10 пудов свинца. Кроме того, на каждого тобольского служилого человека полагалось по фунту свинца. В Березове, куда воеводы пришли на 13 судах, получили они еще скорострельную пищаль и 3 затинных. В наказе говорилось, что воеводы, прибыв в Березов, должны выбрать из зырян и жителей реки Выми тех, кто знает Мангазейский и Енисейский морской ход. А самим им запрещалось без опытных мореходов пускаться в далекое плавание. В наказной памяти упоминалось, что идти надобно «наспех днем и ночью с великим бережением», опасаясь задержки на море. Рекомендовалось по морю идти бережно и в «крепких местах» ставиться «осторожливо на якоря».

Путешествие князя Мосальского и Савлука Пушкина прошло без приключений. В августе они прибыли в Мангазейский острог и отпустили Шаховского и Хрипунова на Русь, приняв от них острожные ключи и «государеву казну».

В опросах поморов-мангазейщиков нашел Данила Наумов сведения о дальнейшей судьбе Леонтия Плехана и его товарищей, об их походе. Рассказал воеводе Ивану Биркину все это сам Плехан.