Из Якутска Дежнев совершил, в составе казачьих отрядов, несколько походов на реки бассейна Лены, побывал на Яне, Моме, Индигирке, Колыме. А затем из Нижне-Колымска отправился на поиски «большой собольной реки». И хотя первая экспедиция закончилась неудачей — льды не позволили Дежневу и его спутникам проникнуть далеко на восток от устья Колымы, — в 1648 году под началом Дежнева и Федота Попова из Нижне-Колымска отправилась новая экспедиция. Все дальше и дальше на восток продвигались суда Дежнева. Было пройдено Чукотское море и обнаружен «Большой Каменный Нос» — северная оконечность гигантского Евразийского материка.
«А с Ковымы-реки идти морем на Анандырь-реку, и есть Нос, вышел в море далеко… а противу того Носу есть два острова, а на тех островах живут чухчи, а ирезываны у них зубы, прорезываны губы, кость рыбий зуб, а лежит тот Нос промеж север на полуношник. А с русскую сторону Носа признака: вышла речка, становье тут у чукоч сделано, что башни из кости китовой. Нос поворотит крутом, к Анандыре-реке подлегло. А доброго побегу от Носа до Анандыра-реки трои сутки, а более нет» — так описал Семен Дежнев «Большой Каменный Нос», ныне по праву носящий имя его первооткрывателя.
Буря в Беринговом проливе «разнесла без вести» суда Дежнева и Попова. «И носило меня, Семейку, по морю после Покрова богородицы всюду неволею и выбросило на берег в передний конец за Анандырь-реку. А было нас на коче всех двадцать пять человек. И пошли мы вое в гору, сами путь себе не знаем, холодны и голодны, наги и босы. И шел я, бедный Семейка, с товарищи до Анандыря-реки ровно десять недель, и попали на Анандырь-реку вниз близко моря, и рыбы добыть не могли, лесу нет. И с голоду мы, бедные, врозь разбрелись. И вверх по Анандыре пошло двенадцать человек, и ходили двадцать ден, людей и аргишниц, дорог иноземских не видали и воротились назад, и, не дошед, за три дня, днища до стану, обночевались, почали в снегу ямы копать» — так повествует Дежнев о своих злоключениях.
Прозимовав на Анадыре, Дежнев и его спутники построили суда и на них поднялись вверх по реке. Там они открыли богатейшее лежбище моржей и обнаружили массу «заморной кости» — ископаемых клыков моржей. В 1660 году с грузом «костяной казны» отправились в обратный путь: сухим путем до Колымы, оттуда морем на Нижнюю Лену. Только в 1664 году добрался Семен Дежнев до Москвы, помимо сведений о далеких, прежде неведомых землях сдав в казну почти триста пудов моржовых клыков.
С 1641 по 1660 год не получал Дежнев никакого жалованья. И теперь царское правительство «по-царски» с ним рассчиталось. Дежнев сдал в казну моржовых клыков на 17 340 рублей серебром. Жалованье за 19-летнюю службу было отпущено ему в размере… 126 рублей 20 копеек. И этой суммы ему не выплатили полностью, ограничившись выдачей из казны 38 рублей. Зато было приказано царем «за его Сенькину службу и на прииск рыбья зуба, за кость и за раны поверстать в атаманы», а само открытие Дежнева было забыто.