Служа затем в отряде Михайлы Стадухина, Дежнёв поздней весной 1643 года прошёл на коче по реке Оймякон до её впадения в Индигирку. Что такое коч? Это большое судно, способное вместить более 30 тонн груза и экипаж численностью до 60 человек. Кочи были специально приспособлены для плавания во льдах, поэтому сооружались они из крепкого леса и снабжались килевым устройством. В условиях Якутии кочи оснащались парусами, сшитыми из оленьих шкур. Деревянные якоря утяжелялись большими камнями.

Воды Индигирки долго несли коч между скалистыми берегами. «А по Индигирке выплыли в море», – писал позже Дежнёв, повествуя об этом плавании. Вообще все его записи, подобно текстам русских летописей, новгородских берестяных грамот и деловых бумаг, отличаются краткостью и плотностью содержания. Этот стиль будет назван в ХХ веке «телеграфным» и сохранится в современных посланиях-«эсэмэсках». Поэтому так легко и воспринимаются сегодня тексты древних новгородских писем и «скасок» русских землепроходцев.

Осенью того же 1643 года Стадухин и Дежнёв объединились с отрядом Дмитрия Зыряна для морского плавания к устью Колымы, которую они открыли во время одного из сухопутных походов. Сейчас тут уже было построено зимовье, позже названное Нижнеколымском. Здесь Семён Дежнёв прожил три года.

Здесь же, в Нижнеколымске, долгими зимними вечерами Дежнёв с товарищами жадно вслушивались в рассказы заезжих служилых и деловых людей о новых, только что открытых землях и водах. Особенный интерес вызвали сообщения Исая Игнатьева по прозвищу Мезенец. Он возглавлял артель из девяти промышленников-поморов, которая всё лето 1646 года провела в поисках «соболиной реки». Мезенец поведал зимовщикам, как поморы на своём коче дошли по морю до Чаунской губы и встретили там чукчей, с которыми провели «немой торг», то есть обмен товарами, в результате которого получили «кости рыбья зуба (моржовые клыки)» и сведения о том, что «на море-де этого зверя много ложится…».

Семена Дежнёва больше привлекала возможность увеличить сбор соболей, и он решил тоже пойти морем на восток от Колымы. В челобитной, поданной начальству, он ручался, что на реке Анадырь соберёт «семь сороков соболей». Как писал в работе «Вечные следы» известный советский историк географических открытий – поэт, писатель и путешественник С.Н. Марков, «Дежнёва причислили к отряду Федота Алексеева Попова Холмогорца, под начальством которого были четыре коча. Летом 1647 года корабли вышли в плавание, но крепкие льды закрыли им путь. Федот Попов и Дежнёв возвратились на Колыму и стали дожидаться более благоприятного для похода времени».

Летом 1648 года Семен Дежнёв снова получил назначение для плавания морем на Анадырь. Но в Сибири тогда промышляли не только охотники и налоговики. Многие «лихие люди» чувствовали себя здесь как рыба в воде. Как в своё время выяснил С.Н. Марков, в этих местах на протяжении около десятка лет орудовал некий атаман Герасим Анкудинов, конкурент Дежнёва, который, прикрываясь служебным положением сборщика ясака, грабил торговых и промышленных людей на Лене, Яне, Индигирке и K°лыме. Узнав, что Дежнёв идет на Анадырь, Анкудинов собрал свою пиратскую шайку. Тридцать головорезов решили разграбить дежнёвские кочи, и с этой целью Анкудинов присоединился самовольно со своим судном к флотилии, находившейся в распоряжении Дежнёва и Попова.

В плавание к Анадырю отправилось 90 человек, считая и анкудиновских молодчиков. 20 июня 1648 года семь кочей, выйдя из Нижнеколымска, двинулись к «великому морю-океану». Когда суда экспедиции шли на восток, разразилась буря, и два судна погибли. Люди сошли с разбитых кочей на берег, но подверглись нападению коряков. В схватке много русских было убито, а те, кто уцелел, остались жить у моря. Остальные пять кораблей продолжали свой путь. Около 20 сентября Дежнёв и его спутники увидели тёмный и грозный мыс – Большой Каменный Нос, окаймлённый полосой пенных бурунов. Мимо этого Каменного Носа прошли из Северного Ледовитого в Тихий океан лишь три коча – суда Дежнёва, Попова и Герасима Анкудинова, а два других корабля побила буря. В конце пролива между Азией и Америкой нашел свою гибель и коч Герасима Анкудинова. Дежнёву пришлось пустить пиратов на свой корабль. Таким образом, несмотря на все препятствия и потери, впервые в истории мореплавания был осуществлён переход из Северного Ледовитого океана в Тихий.

Позже Дежнёв писал в одной из своих челобитных: «…а тот Нос вышел в море гораздо далеко, а живут на нем люди чухчи добре много. Против того же Носу на островах живут люди, называют их зубатыми, потому что пронимают они сквозь губу по два зуба немалых костяных… А тот Большой Нос мы, Семейка с товарищами, знаем, потому что разбило у того Носу судно служилого человека Ярасима Онкудинова с товарищами. И мы, Семейка с товарищи, тех разбойных людей имали на свои суды и тех зубатых людей на острову видели ж». А вскоре после этого исчез в Тихом океане коч Попова. «И того Федота со мною, Семейкою, на море разнесло без вести», – писал Дежнёв.

По авторитетному мнению И.П. и В.И. Магидовичей, под «Большим Каменным Носом» Дежнёв понимал не только мыс, носящий ныне его имя, но и весь Чукотский полуостров, а островами «зубатых» людей могут быть Аракамчечен и Ыттыгран.

Первого октября 1648 года опять разразилась буря. Дежнёвский коч долго носило по морю и выбросило на берег где-то вблизи Олюторского полуострова. Сам он писал об этом так: «И носило меня, Семейку, по морю после Покрова Богородицы всюду неволею и выбросило на берег в передний конец за Анадырь-реку. А было нас на коче всех двадцать пять человек». Олюторский полуостров расположен в 900 км к юго-западу от Чукотского мыса. Оттуда потерпевшие кораблекрушение двинулись на северо-восток: «А пошли мы все в гору, сами пути себе не знаем, холодны и голодны, наги и босы. А шел я, бедный Семейка, с товарищи до Анадыря-реки ровно десять недель, и попали на Анадырь-реки вниз, близко моря, и рыбы добыть не могли, лесу нет. И с голоду мы, бедные, врознь разбрелись. И вверх по Анадырю пошло двенадцать человек и ходили двадцать дён, людей и оленьих упряжек, дорог иноземских не видали. И воротились назад и, не дошед, за три днища до стану, обночевались, почали в снегу ямы копать…». Отсюда следует, что Дежнёв не только открыл, но и первый пересек Корякское нагорье и 9 декабря 1648 года вышел в низовье Анадыря.

Девятеро из ушедших (это были как раз «буйные молодцы» Анкудинова) не стали возвращаться в отряд, и их дальнейшая судьба неизвестна. Лишь трое пиратов (теперь уже бывших) присоединились к Дежнёву. Сейчас очень трудно представить себе жизнь этих пятнадцати отчаянных людей, которые не только выжили, но и сумели построить речные лодки. Это было весной 1649 года.

На верхнем течении Анадыря русские встретили кочевых анаулов – незнакомое им юкагирское племя. Произошёл очередной «контакт цивилизаций»: когда Дежнёв, не забывавший о своей обязанности «мытаря», стал брать с анаулов ясак, аборигены отметили его «смертной раною». Но Дежнёв выжил. Его команда приступила к постройке острожка на Анадыре. Землепроходцы жили теперь за крепкими стенами, срубленными из вековых лиственниц и обведёнными глубоким рвом. Так началось заселение русскими людьми новых земель на берегах Тихого океана.

В 1652 году анадырские служилые выбрали Дежнёва своим начальником, то есть «приказным человеком». Тем же летом Семён Дежнёв и Никита Семёнов, совершив плавание на кочах вниз по Анадырю, открыли в устье реки богатейшее лежбище моржей. Там начался прибыльный промысел, который потребовал пополнения «живой силой и техникой». Заселение Чукотки русскими людьми продолжалось.