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