Ко времени перевода в Удьский острог у Атласова и его жены Степаниды были уже двое сыновей.
Уже в первый год своей службы в Якутске Атласов совершил ряд злоупотреблений своим служебным положением, он насильственно изымал ясак у якутов в свою пользу. Эти конфискации сопровождались побоями местных аборигенов. Якуты подали жалобу в приказную избу, и делу был дан ход. Однако свидетелей по делу о нанесении якутам обиды не нашлось, и основным обвинением, которое вынесли Атласову, было нанесение побоев местному населению. Хищения ясака обнаружено не было.
По приговору суда Атласов был бит кнутом и с него взяли поручную запись, «что он впредь не станет и воровать и не озорничать».
В 1690 году Атласов был отправлен на службу в Анадырский острог.
Анадырский острог возник из зимовья, поставленного в 1б49 году Семеном Дежневым, попавшим на Анадырь после его путешествия вдоль побережья Чукотского полуострова. В 1660 году присланный на смену Дежневу сын боярский Кур-бат Иванов решил укрепить стоявшее на острове зимовье и превратил его в острог.
Но служба Атласова в Анадырском остроге продолжалась недолго. У него возник конфликт с приказчиком острога Григорием Чернышевским, и Атласов был снова бит батогами и отправлен в Якутск с казной.
Здесь у него произошла встреча с якутским воеводой Иваном Матвеевичем Гагариным, которому Атласов сообщил, что можно попасть на Камчатку из Анадырска, двигаясь через земли пенжинских коряк. Атласов же сообщил Гагарину, что камчатская земля богата соболями. Он обещал воеводе, что отряд для похода на Камчатку будет сформирован им на собственные средства. Единственной просьбой Атласова было повышение его в следующий чин, что дало бы ему в будущем возможность претендовать на должность приказчика Анадырского острога.
Просьба Атласова была удовлетворена, но поскольку численность Анадырского гарнизона была невелика, новому приказчику пришлось набирать в свой отряд «охочих людей» в виде своих покрученников.
Заняв подводы и лошадей у местных крестьян, Атласов с отрядом в 13 человек переправился на правый берег Лены и двинулся к ее притоку Алдану. Здесь он переплыл на лодках и пошел в район реки Тукукан, где существовала переправа. Дальнейший его путь проходил по правому берегу Тукукана. После преодоления небольшого горного хребта, отряд Атласова вышел на реку Яны, где продвигался по льду, сковывавшему ее течение.
Спустя две недели отряд Атласова добрался до Верхоянского зимовья, где несколько дней отдыхал, а также нанимал лошадей у местного населения.
Через несколько дней отряд Атласова вновь начал продвижение по льду Яны до устья реки Тостая, впадавшей в Гиленду. Пройдя шесть-семь недель долгого пути, отряд Атласова остановился в Индигирском острожке. Сильный мороз и глубокий снег не давали возможности ехать на лошадях, и отряд Атласова пересел на оленьи упряжки. Дальнейший их путь пролегал к Алазейскому зимовью и далее к устью Колымы. Конечной целью путешественников был Анадырский острог, где Атласов должен был сменить Михаила Многогрешного, бывшего приказчика острога.
Прибыв в Анадырский острог, Атласов узнал, что незадолго до его приезда Многогрешный послал на Камчатку отряд из 50 человек во главе с Лукою Морозко Старициным. Скоро члены вернувшейся экспедиции рассказали новому приказчику о том, что на Камчатке они видели «немирных коряк», разбили их острогу и привели в качестве аманатов двух ясачных князьцов, Эвонту и Инону. Говорили казаки также и о собранном ясаке в виде лисьих и собольих шкурок.
Атласов сам поспешил на Камчатку, чтобы собственными глазами увидеть земли, в которых уже побывали люди из Анадырского острога. Его отряд состоял из 120 человек, половина из них была служилыми и промышленными людьми, вторую половину составляли ясачные оленные юкагиры.
Двигаясь к югу, отряд Атласова в январе 1697 года достиг реки Пенжины. Вдоль морского побережья Камчатки до реки Тегиль тянулись поселения коряков.
Здесь его догнали казаки Морозко и Голычин, которых Атласов оставил в Анадырском остроге, не взяв в новую экспедицию. Несмотря на то что такая встреча никак не могла быть приятной Атласову, он не стал затевать свары и продолжал путь по полуострову.