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