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