К тому времени у «Ламского окияна» побывало уже несколько отрядов первопроходцев. В начале 1642 года к устью реки Охоты, пройдя через якутский Оймякон, полюс холода, вышел отряд казака Андрея Горелого, 18 русских и 20 якутов. Осенью 1645 года на берегах Охотского моря зазимовал отряд Василия Пояркова, который первым в русской истории проплыл по Амуру и теперь искал пути возвращения на реку Лену. Известно, что Поярков родился в самом центре европейской России, в городке Кашин (ныне в Тверской области), так что его место зимовки от места рождения отделяло пять с половиной тысяч вёрст – расстояние огромное и в наше время, а тогда просто фантастическая даль, на преодоление которой требовались годы…
Ещё казаки Москвитина, первыми оказавшиеся на берегах «Ламского моря», советовали начальству «чтоб на той Охоте реке поставить острожек крепкой, и соболей и лисиц будет много». Поэтому летом 1646 года, изучив полученные от людей Москвитина «скаски»-донесения, из Якутска к берегам Охотского моря отправился большой отряд, 40 человек, под командованием казачьего десятника Семёна Андреевича Шелковникова.
В мае 1647 года казаки Шелковникова, двигаясь по пути разведанному отрядом Москвитина, вышли к «Ламскому окияну». Здесь к ним присоединились остатки отряда Пояркова, и совместными силами шесть десятков первопроходцев 23 мая 1647 года в устье реки Охоты, в трёх верстах от морского побережья, на берегу протоки Амунки было основано укреплённое зимовье. Так на дальневосточном побережье современной Российской Федерации возникло первое русское поселение.
Рождение будущего Охотска не было мирным. Казакам Шелковникова пришлось выдержать настоящую битву с местными «ламутами»-эвенами, которые не желали платить пришлыми чужакам дань мехом соболей и лисиц. Как позднее докладывали казаки начальству в Якутск «ясачной сборщик служилый человек Семейка Шелковник за большим боем Охоту взял и зимовье поставил».
Охотское зимовье стало базой для дальнейшего освоения берегов «Ламского моря-окияна». Так летом следующего после основания 1648 года отправленный Шелковниковым из Охотска отряд под началом Алексея Филипова и Ермила Васильева, двигаясь на северо-восток, достиг побережья Тауйской губы, то есть района современного города Магадан. Здесь они обнаружили лежбища тысяч моржей, «где зверь морж ложится» – моржовые клыки, или «рыбья кость», как их тогда называли, ценились не меньше, чем самые драгоценные меха. За пару моржовых клыков, привезенных с берегов Охотского моря, в XVII веке в Москве можно было купить целый дом.
Но доставались такие богатства нелегко. К 1649 году, когда в устье Охоты был построен «косой острожек», укрепленный частокол из заострённых бревен, почти треть отряда Шелковникова погибла в боях с эвенами или умерла от голода и лишений. Скончался и сам Шелковников, ему на смену с берегов реки Лены вместе с подкреплениями прибыл «служилый человек, приказный Якутского зимовья» Семён Епишев, ставший вторым главой Охотска. Весной 1651 года Епишев обнаружил в острожке лишь «чуть живых двадцать человек».
Весной 1652 года, когда большая часть охотских казаков разъехалась собирать меховую дань с окрестных племён, «острожек» осадили восставшие «ламуты». Небольшой русский гарнизон, около 30 казаков, пробился из окружения и отступил южнее, к реке Улье. Постройки и укрепления первого Охотского острога «ламуты»-эвены сожгли.
Но, не смотря на все трудности и сложность дальнего пути, власти российского государства оценили стратегическое значение Охотского побережья. Отныне сюда из Якутска каждый год стали направляться новые отряды для изучения открытых земель и сбора меховой дани.
В 1654 году отряд «сына боярского» Андрея Булыгина восстановил Охотский острог и его укрепления. Как писал сам Булыгин в донесении начальству: «Послан я, Ондрюшка, з государевыми служилыми людьми на государеву дальную службу на Ламу на Большое море-акиян, на Улью, и на Охоту, и на Нию, и на Мотыхлей реки для государева ясачново соболиного збору и для прииску и приводу под государеву царскую руку немирных иноземцов тынгусов… И после того я, Ондрюшка, с служилыми людьми на Охоте реке острог поставили мерою в длину 20 сажен, а поперег 10 сажен».
Построенный «сыном боярским» Булыгиным острог был всего около 40 метров в длину и 20 метров шириной. По площади это меньше, чем привычный нам стандартный многоквартирный дом с тремя подъездами, но в то время для Сибири и Дальнего Востока это был крупный посёлок, почти город.
Помимо строительства острога, Андрей Булыгин в 1654 году отправил в Якутск собранную с окрестных эвенов меховую дань – 264 драгоценных шкурки соболей и чернобурых лисиц. В Москве того времени такой «ясак» оценивался в несколько тысяч серебряных рублей, целое состояние!