Просьба Атласова была удовлетворена, но поскольку численность Анадырского гарнизона была невелика, новому приказчику пришлось набирать в свой отряд «охочих людей» в виде своих покрученников.
Заняв подводы и лошадей у местных крестьян, Атласов с отрядом в 13 человек переправился на правый берег Лены и двинулся к ее притоку Алдану. Здесь он переплыл на лодках и пошел в район реки Тукукан, где существовала переправа. Дальнейший его путь проходил по правому берегу Тукукана. После преодоления небольшого горного хребта, отряд Атласова вышел на реку Яны, где продвигался по льду, сковывавшему ее течение.
Спустя две недели отряд Атласова добрался до Верхоянского зимовья, где несколько дней отдыхал, а также нанимал лошадей у местного населения.
Через несколько дней отряд Атласова вновь начал продвижение по льду Яны до устья реки Тостая, впадавшей в Гиленду. Пройдя шесть-семь недель долгого пути, отряд Атласова остановился в Индигирском острожке. Сильный мороз и глубокий снег не давали возможности ехать на лошадях, и отряд Атласова пересел на оленьи упряжки. Дальнейший их путь пролегал к Алазейскому зимовью и далее к устью Колымы. Конечной целью путешественников был Анадырский острог, где Атласов должен был сменить Михаила Многогрешного, бывшего приказчика острога.
Прибыв в Анадырский острог, Атласов узнал, что незадолго до его приезда Многогрешный послал на Камчатку отряд из 50 человек во главе с Лукою Морозко Старициным. Скоро члены вернувшейся экспедиции рассказали новому приказчику о том, что на Камчатке они видели «немирных коряк», разбили их острогу и привели в качестве аманатов двух ясачных князьцов, Эвонту и Инону. Говорили казаки также и о собранном ясаке в виде лисьих и собольих шкурок.
Атласов сам поспешил на Камчатку, чтобы собственными глазами увидеть земли, в которых уже побывали люди из Анадырского острога. Его отряд состоял из 120 человек, половина из них была служилыми и промышленными людьми, вторую половину составляли ясачные оленные юкагиры.
Двигаясь к югу, отряд Атласова в январе 1697 года достиг реки Пенжины. Вдоль морского побережья Камчатки до реки Тегиль тянулись поселения коряков.
Здесь его догнали казаки Морозко и Голычин, которых Атласов оставил в Анадырском остроге, не взяв в новую экспедицию. Несмотря на то что такая встреча никак не могла быть приятной Атласову, он не стал затевать свары и продолжал путь по полуострову.
Отряд Атласова перешел Корякский хребет и поспешил в сторону восточного побережья Камчатки для сбора ясака с опукских коряков. Опукцы не только дали казакам ясак, но даже указали им верные пути к своим соседям, жившим на побережье Олюторского залива.
Направив Луку Морозко дальше исследовать берега восточной Камчатки, сам Атласов повернул на западный (Пен-жинский) берег и продолжил его обследование.
Однако Атласов скоро убедился, что далеко не все коряки будут охотно платить им ясак. Чем более он углублялся в земли полуострова, тем чаще между его казаками и местными аборигенами происходили столкновения. Из 60 человек отряда Атласова лишь 30 были способны носить оружие, остальные были юкагиры — погонщики оленей. Юкагиры жаловались Атласову, что он не выполняет обещаний, данных им перед началом похода — не обеспечил свободную охоту на пушного зверя и добычу «погромных» оленей, взятых у «немирных» коряков. Однако Атласов торопил участников похода двигаться быстрее, а казаки, в свою очередь, не рисковали штурмовать укрепленные острожки на высоких каменных утесах.
Над самим Анадырским острогом нависла серьезная опасность. Перед выступлением в поход большая часть Анадырского гарнизона ушла вместе с Атласовым к Камчатке, и теперь юкагиры, жившие вблизи Анадырска, мечтали напасть на оставшихся в остроге казаков и перебить их. Тесную связь анадырские юкагиры поддерживали и со своими соплеменниками, ушедшими вместе с Атласовым. Вначале они решили перебить служивых казаков, а затем уже, соединившись с земляками, покончить с Анадырским гарнизоном.
Сумев разъединить отряд Атласова, юкагиры объединились с коряками, отказывающимися платить ясак, и на рассвете напали на лагерь, поведя его обстрел из луков. В первые же минуты нападения были убиты три и ранено 15 человек. Атласов получил шесть ран.
Казаки повели стрельбу из пищалей и начали возводить укрепления из саней, чтобы закрыться от стрел, летящих со всех сторон. Под покровом темноты Атласов послал верного юкагира за помощью к Луке Морозко, а сам засел в долгую осаду. Юкагиру удалось добраться до Морозко и сообщить ему о беде, постигшей отряд Атласова. Прервав движение по восточному берегу, отряд Морозко подошел к русскому лагерю и ударил осаждающих с тыла. Коряки бежали, юкагиры начали просить о пощаде.
Атласов приказал наказать 30 юкагиров батогами, после чего большая их часть бежала на Анадырь. Здесь они сообщили старейшинам о неудачной попытке расправиться с русским отрядом, и те поняли, что возможности напасть на острог они уже лишились.
На Тигиле в отряде Атласова начались разногласия, каким маршрутом двигаться дальше. Атласов хотел по-прежнему идти по западному берегу полуострова, другие члены отряда говорили о необходимости повернуть в глубь полуострова до реки Камчатки. И Атласову пришлось согласиться с мнением большинства членов экспедиции.
По течению реки Еловки отряд Атласова вышел к реке Камчатка. Здесь им стали встречаться острожки местных жителей — камчадалов. Встреча с аборигенами носила достаточно миролюбивый характер. Атласов объявил камчадалам, что его отряд послан в их землю от имени русского царя для защиты от врагов. А затем Атласов раздал аборигенам подарки — бисер и другие украшения.
Камчадалы стали зазывать казаков в свои дома-острожки, показывая им свое хозяйство.
Старейшины камчадалов рассчитывали на помощь отряда Атласова в своей борьбе с соседними племенами с низовьев реки Камчатки, которые недавно погромили их острожки. Атласов обещал оказать эту помощь, но предварительно послал Луку Морозко разведать земли других камчадалов.
Отряд Атласова пополнился новыми воинами-камчадалами. Однако вооружены они были топорами и ножами из отшлифованного камня или из отточенной оленьей и китовой кости. Стрелы и копья имели наконечники из собольих костей, а тетива лука была сделана из китового уса.
Воины-камчадалы были одеты в панцири (куяки), также сделанные из мелких косточек.
Путь к противникам камчадалов лежал по реке, по которой отряд Атласова должен был плыть в лодках (батах). В каждой лодке размещалось по 2 человека.
Три дня отряд Атласова двигался вниз по течению. По пути им попадались поселения камчадалов, в которых Атласов сознательно не останавливался до тех пор, пока не добрался до наиболее крупных селений, в которых стояло около 400 юрт. Навстречу отряду вышли 400 воинов, вооруженных подобно камчадалам отряда Атласова.
Командир отряда предложил камчадалам подчиниться царю и платить ясак. Однако старейшина враждебного племени отказался это сделать, и тогда Атласов приказал дать несколько выстрелов из пищалей, а затем поджечь все балаганы и взять пленных, которых передал своим союзникам.
Камчадалы разбежались по окрестностям, где рассказали своим соплеменникам, жившим по берегам реки Камчатки, о встрече с пришельцами. Среди камчадалов началась паника. На обратном пути Атласов завернул в острожки, мимо которых ранее прошли его лодки, и потребовал у их жителей выплаты ясака. Камчадалы согласились, но стали просить отсрочки, на что Атласов согласился. Он понимал, что мех соболя летом не представлял особой ценности, поскольку в это время зверь линял.
Атласов договаривался с камчадалами, что зимой они займутся промыслом соболя, чтобы к следующей весне сдать его в качестве ясака. Летом 1697 года Атласову удалось пройти до верховья реки Камчатки, где он построил Верхнекамчатское зимовье. Таким образом, большая часть полуострова перешла под власть отряда Атласова, и тогда руководитель экспедиции решил увековечить присоединение полуострова к России. 23 июля 1697 года на левом притоке Камчатки, речки Крестовой (Канучь), был воздвигнут крест, простоявший здесь почти сорок лет. Так мы знаем теперь официальную дату присоединения Камчатки к России.
Осенью Атласов вместе с отрядом вернулся на речку Еловку, где решил провести зиму в сооруженном зимовье. В это время года они занимались соболиным промыслом с помощью луков и сетей. Весной шкурки разбирались по сортам и связывались в «сороки» (по 40 штук в каждой), а затем помещались в кожаные мешки («козлы»).
Весной Атласов вновь двинулся по течению Камчатки, чтобы собрать ясак с камчадалов, с которыми он еще в прошлом году договорился о его уплате. Некоторые камчадалы выплатили ясак, но иные решили оказать казакам сопротивление, запершись в своих острожках. Из-за частокола, которым были ограждены юрты, мужчины-камчадалы кидали в русских палки, колья и камни. Приходилось, прикрывшись щитами, поджигать острожки, предварительно выставив засаду у ворот. Лишь тогда удавалось собрать с камчадалов ясак.
Как только Атласов вернулся в зимовье на Еловке, он узнал, что коряки угнали с пастбищ у верховьев Тигила стада оленей. Потеря оленьих стад грозила большими неприятностями отряду Атласова — он мог лишиться как продовольствия, так и средств передвижения. Оставив в зимовье Луку Морозко для контроля над Тигильско-Еловской дорогой на Камчатку, Атласов поспешил к устью Тигила. Здесь он догнал коряков с угнанными у него оленьими стадами, однако те не захотели их вернуть миром и вступили в бой. В конечном итоге оленьи стада были отбиты и отряд Атласова двинулся вдоль берега Пенжинского моря, откуда направился на реку Ичу.
Здесь он обнаружил новые поселения камчадалов, с которыми вступил в дружеские отношения, раздавая подарки. Зная, что с Ичи ведет дорога в верховье реки Камчатки к Верхнекамчатскому зимовью, Атласов направил по ней своего служилого человека Потапа Серюкова для сбора с местных жителей ясака.
Сам же он двинулся к Менжинскому побережью полуострова. К этому его подталкивала необходимость пополнить свой отряд оленями, в которых у него явно ощущался недостаток. Но коряки, узнав о приближении отряда Атласова, убежали со своих кочевий и угнали с собой оленей. Атласов кинулся в погоню за коряками, преследование продолжалось около шести недель. Лишь только тогда, когда путь беглецам преградила быстрая река Кыкша, коряки остановились. Однако и здесь они отказались выплачивать ясак оленями и признавать подданство русского царя. Только после жестокого боя удалось отбить оленье стадо, и отряд Атласова двинулся западным берегом Камчатки. Вскоре он достиг реки Нинчуги, за которой начинались поселения курилов.