Чтобы закрепиться в земле воинственных юкагиров, предстояло создать опорные пункты, укрепленные острожки. Среди исследователей долго бытовало мнение, что, достигнув морем Колымы, Стадухин с Зыряном и их спутниками поставили невдалеке от устья ясачное зимовье, огороженное частоколом и получившее название Нижнеколымского острожка или Нижнеколымска. Оно и считалось самым первым русским селением на Колыме.
Найденная Б.П. Полевым в Центральном государственном архиве древних актов (ЦГАДА) челобитная М. Стадухина и его товарищей об открытии Колымы в 1643 году позволяет нам внести серьезные уточнения. Из этого важного исторического документа видно, что 15 июля где-то в низовьях реки отряд Стадухина и Зыряна столкнулся с «оленными людьми», предводительствуемыми князцами Пантели и Ралю. Неясно, что это были за люди — чукчи или юкагиры. «Оленные люди» воспрепятствовали русским обосноваться в низовьях Колымы. Стадухинцам пришлось прорываться вверх по реке. «Оленные люди», по-видимому, обладавшие большим численным превосходством, преследовали русских на лодках. Только через три дня стадухинский отряд смог оторваться от погони. Русские подымались вверх по реке до 25 июля, достигнув селения оседлых юкагиров-омоков, во главе которых стоял князец Алай. Здесь, «на его Олаевых житьях», Стадухин и его товарищи поставили острожек.
Анализ стадухинской челобитной и других документов позволяет установить, что речь идет об основании Среднеколымска, который и следует считать первым русским поселением на Колыме. Там поселились первые колымские «начальные люди», хранилась до отправки в Якутск собранная на Колыме соболиная казна. В ближайшие годы были основаны Верхнеколымское и Нижнеколымское зимовья, и таким образом русский контроль охватывал весь Колымский край.
Выбирая местоположение для русского поселения на Колыме, пока еще единственного, Стадухин и его товарищи руководствовались несколькими весомыми соображениями. По среднему течению реки обитало оседлое население, с которого легче было собирать ясак, тогда как в низовьях Колымы пришлось бы сталкиваться с кочевниками, которые в любой момент могли откочевать в иное место. К району Среднеколымского зимовья сравнительно близко подходила верхняя Алазея, до которой, как сказывали местные юкагиры, можно было добраться за три дня. Предводители казачьего отряда рассчитывали по-прежнему собирать ясак с алазейских юкагиров. Для этой цели местоположение Среднеколымского зимовья было наиболее удачным. В ранних колымских ясачных книгах можно найти упоминание о получении ясака с юкагиров, обитавших на Алазее. На Индигирку первые сведения об успешном походе Стадухнна и Зыряна на Колыму были доставлены алазейскими юкагирами, ходившими «по вся годы на Ковыму реку к ковымскнм мужикам, к пешим и оленным в гости».
Наконец, в выборе места для поселения на Колыме, когда на ней еще не было других зимовий, немаловажную роль сыграло и то, что до Среднеколымска могли свободно подниматься морские кочи. Зимовье это находилось примерно на равноудаленном расстоянии от устья до верховьев реки, и это давало возможность посылать экспедиции для сбора ясака по всему Колымскому краю.
Среднеколымские юкагиры-омоки, состоявшие из трех родов: Калянина, Аливина и Алаева, попытались было оказать сопротивление установлению русской власти. Стадухин и Зырян были вынуждены предпринять поход против «юкагирских мужиков-омоков». Завязался бой. Русские отвечали на юкагирские стрелы залпами из пищалей, сходились врукопашную.
Дежнев отличился в бою, убив «лутшево мужика Алаева брата». Сам Алай считался одним из самых влиятельных юкагирских князцов на Колыме. Русские смогли взять в плен Алаева сына Кениту и другого юкагира — Каляну. Их содержали в качестве аманатов в Среднеколымском зимовье. В бою Дежнев снова был серьезно ранен. «А меня, — писал он, — холопа твоего, в левую руку по завити железницею насквозь прострелили».
Юкагирские князцы признали свое поражение и согласились платить ясак. Между русскими и юкагирами наладились мирные отношения. В Среднеколымском зимовье шла оживленная меновая торговля. Сюда съезжались окрестные юкагиры, чтобы выменять шкурки на домашнюю утварь и другие полезные в хозяйстве предметы. Пополнялась мягкой рухлядью ясачная изба. Собирая ясак, казаки посещали ближние и дальние поселенья и кочевья юкагирских родов.
Так продолжалось три года. Пообносились казаки, истосковались по хлебу, питаясь рыбой, олениной, грибами да ягодами. В 1645 году Стадухин и Зырян решили с половиной отряда и собранным ясаком плыть морем до ленского устья, а далее Леной до Якутска. На Колыме осталось всего тринадцать человек во главе с Семеном Дежневым и Вторым (Втором) Гавриловым.
Проведал злопамятный князец Алан, тот самый, брата которого убил собственноручно Дежнев, что опустел острожек и осталась в нем лишь малая горстка защитников. Целая орда, человек пятьсот, под предводительством Алая, ринулась на штурм острожка. Не остановили их натиска защитники и «огненным боем». Падал один из нападавших, а десятки устремлялись вперед. Пока успевали русские перезарядить пищали, Алаевы воины карабкались на частокол и врывались вовнутрь острожка, испуская воинственные возгласы. Положение защитников становилось критическим.
С отчаянной отвагой бросились русские в рукопашный бой. Все они были ранены, а Дежнев получил ранение в голову железной стрелой. Но и истекающие кровью продолжали сражаться. Один из казаков, пробивая себе дорогу сквозь толпу нападавших, сошелся с самим князцом Алаем и «твоим, великого государя, счастием, изменника Алайка не съемном бою копьем сколоти до смерти», — как сообщал позже Дежнев.
Гибель князца вызвала в рядах нападавших замешательство. Дрогнули их ряды. Не устояли перед отчаянной отвагой защитников и «убояси смерти, отошли прочь от острожку».
Дмитрий Зырян не доехал до Якутска. На море он встретил кочи с большой партией ленских торговцев и промышленников во главе с целовальником Петром Новоселовым. Воевода Петр Головин отсылал с Новоселовым на имя Зыряна наказную память о назначении его целовальником (правительственным приказчиком) на сдальние реки». Дмитрии Зырян был вынужден возвратиться на Колыму, тогда как Стадухин с пушниной добрался до Лены.
Возвращение Зыряна на Колыму в роли приказчика-целовальника поставило Семена Дежнева под его начало. Об этой службе Дежнев пишет: «И он приказной Дмитрий Михайлов и целовальник Петр Новоселов тебе, государю, радели с великим радением — посылали нас, холопей твоих, на непослушников, неясачных иноземцов, и голов своих не щадили, и кровь свою проливали… и голод терпели и всякую нужу принимали, и твой, государ, ясак мы, холопи твои, с неясачных людей збираем с великим раденьем».
Дежнев становится во главе отряда численностью более тридцати человек, который по приказу Зыряна и Новоселова выступил в поход против непокорных юкагиров. В результате боя был взят в аманаты некий Аливин, сын Черма. В бою Дежнев вновь был ранен: «а меня, холопа твоего Сеньку, на той имке те юкагиры ранили в левую руку под мышку». Из этого сообщения самого Семена Дежнева видно, что он, не обладая в то время никакими начальственными чинами, занимал положение далеко не рядового казака. Выделяясь среди товарищей боевой доблестью, он получает командование над крупным отрядом. Выносливый, дерзкий и отважный в бою, но не безрассудно-отчаянный, готовый протянуть руку противнику, чтобы избежать ненужного кровопролития, Дежнев завоевал среди казаков заслуженный авторитет.
Тем временем Колыма привлекает торговых и промышленных людей, которые толпами устремлялись сюда. В июле 1647 года якутская таможня выдала проездные грамоты «вниз по Лене и морем на Колыму и Индигирку для торгу и промыслу» 404 человекам Среди них были приказчики крупных московских купцов, монастырей, например Аитониева Сийского монастыря под Холмогорами, а также близких к царю знатных вельмож, таких, как боярин Романов. Каждый приказчик располагал вооруженным отрядом, состоявшим из покручеников и наемных людей, которые занимались непосредственным промыслом, управляли кочами, охраняли имущество.
