Особенно недоволен остался Курбат Иванов состоянием зимовья, небольшого поселения, почти лишенного укреплений. По убеждению нового администратора, русские должны были располагать на Анадыри надежным опорным пунктом с прочными башнями и стенами, способными в случае необходимости выдерживать длительную осаду со стороны неприятеля. Здесь проявились два подхода. Дежнев, сторонник мягких, гуманных методов обращения с аборигенами края, не считал необходимым бряцать без нужды оружием и жил, по мнению Курбата, «оплошливо», не заботясь о возведении укреплений. Как справедливо пишет М.И. Белов: «В годы своего правления благодаря мягкому, но волевому характеру, вдали от опеки якутской администрации Дежневу удалось ладить с юкагирами. Конечно, идеализировать его отношения к местному населению ни в коем случае нельзя, но что оно, несмотря на присущую той эпохе суровость, являлось благожелательным, представляется бесспорным. При этих условиях Дежневу не очень-то нужен был острог. По существу, он был скорее промышленник, чем ясачный сборщик».
Все наличные силы Курбат Иванов мобилизовал на заготовку леса и строительство острога. Возводились новые избы, хозяйственные постройки, крепкие стены с башнями. Как писал Курбат воеводе: «В прошлом 168 (1660) году поставил я, Курбатко, острог и в остроге аманатцкую избу с нагороднею, и со всякими крепостьми, и зимовье построил, и в остроге государев амбар с служилыми и охочими промышленными людьми».
Летом 1660 года Курбат Иванов организовал и сам возглавил большую морскую промысловую экспедицию к северо-восточным берегам Чукотки, В ней приняли участие и некоторые из старых соратников Дежнева. Одной из задач экспедиции были поиски новых Моржовых лежбищ. В этом были заинтересованы и якутские власти. Направляя Курбата на Анадырь, воевода указывал в «наказной памяти», что открытие новых моржовых лежбищ будет поощрено освобождением промышленников от уплаты десятинной пошлины и другими привилегиями.
Плавание было исключительно трудным. На восьмой день плавания коч оказался сильно поврежденным штормом. Мореплаватели вытащили судно на берег и занялись его починкой. Не раз приходилось вступать в бой с чукчами. Кончились запасы продовольствия. Приходилось питаться грибами. С чукчами, видимо, удалось в конце концов замириться и даже раздобыть у них оленины.
Коч Курбата Иванова дошел до «Большой губы». По-видимому, речь шла о заливе Креста. Не обнаружив нигде моржового лежбища, отряд вышел в обратное плавание. В Анадырском заливе коч снова попал в страшную бурю. Пришлось выбросить за борт все припасы, чтобы поднять осадку. Мореплаватели натерпелись всяких бед, так что, по словам Курбата, «чаяли себе смерть».
Так морской поход Алексеева — Дежнева вокруг Чукотки положил начало русским плаваниям по Берингову морю. Вторым плаванием стала экспедиция Курбата Иванова. Неласково встречало Берингово море мореплавателей, жестокими бурями и штормами. Но начало освоению северной части Тихого океана было положено.
Увидел Семен Иванович новый острог завершенным или нет — мы не знаем. Он покинул Анадырь зимой 1660 года, пробыв двенадцать лет в суровом Анадырском крае и покинув Якутск около двадцати лет тому назад. При нем был большой груз — более 150 пудов моржовой кости я, вероятно, почта, которой его снабдил Курбат Иванов. Вместе с Дежневым отправился в путь один из его старых товарищей, Артемий Солдатко. Шли они до Колымы обычным сухим путем — через вершину Анадыря, Анюйский камень, Антон. Этим путем не раз ходили в том и ином направлении русские люди, служилые, торговые, промышленные. Тем не менее он оставался плохо освоенным, тяжелым. Бывало, путники блуждали по горной тундре и каменистым кручам на водоразделе между верховьями рек Анадыри и Анюя, страдали от голода и холода. Выходили обычно по санному пути, пользуясь нартами в оленьих и собачьих упряжках, чтобы к исходу весны достичь желанной цели. О своем путешествии с Анадыри на Колыму, преодолении наиболее трудного участка пути Дежнев не оставил нам никаких свидетельств. Весьма вероятно, что ему оказали помощь проводники-анаулы, с которыми у него сохранились добрые отношения. В Нижнеколымске Семен Иванович встретил старого знакомого Ивана Ерастова, который был когда-то рядовым казаком, а теперь стал сыном боярским и приказным на Колыме. Он и помог Дежневу. Летом 1661 года Семен Иванович смог погрузить костяную казну на коч Ерастова, который по окончании своей колымской службы возвращался в Якутск. Корабль вышел в море и взял курс на запад, к устью Лены.