Вернувшись из алданской экспедиции, Атласов занялся устройством отцовского наследства. Очевидно, раньше для этого не было времени. Он пытался взыскать различные долги и подал множество челобитных, но особого успеха не добился. Судя по сохранившимся документам, должники не собирались ничего возвращать, пользуясь ситуацией. Да и времени у казака на долгие судебные разбирательства тоже не было. В августе 1684 г. его под началом казацкого пятидесятника Андрея Амосова отправили на далекую реку Уду. Было известно, что на Уде «прокорму мало», то есть необходимо было брать с собой запас продовольствия. Оказалось, что это не только неудобно, но и опасно: по пути, в зимовье Маймаканском, на Атласова и его казаков напал отряд казака Лариона Дурнева и забрал все припасы. В результате на Уде Атласову пришлось несладко. Жили впроголодь, хотя время от времени ходили в дальние экспедиции, чтобы пополнить запасы рыбы и мяса, в частности, впервые побывали на реке «Хамун» (Амгунь).
Такая жизнь изрядно надоела землепроходцу, и Атласов договорился с одним из служивших с ним казаков Василием Протасовым, что тот займет его место. Василий согласился и написал в Якутск челобитную с просьбой отозвать Атласова. Примерно в это время Амосов получил сообщение о том, что на Алабазин и Удский острог готовится нападение. С донесением по этому поводу в Якутск он направил Атласова.
В Якутске Атласов задержался: у него родился сын Иван, и казак, конечно, рад был побыть в кругу семьи. Однако в августе 1687 г. пришлось вернуться на Уду с отрядом казаков Ивана Крымова, которому он служил провожатым. Перезимовав в Удском остроге, Атласов вернулся в Якутск и вновь попытался заняться хозяйством. Добился выделения отдельного двора и огорода, поскольку до этого семья жила с братьями Атласова, Иваном и Григорием, в отцовском доме.
Волевой и жесткий характер бывалого казака понравился новому якутскому воеводе, чрезвычайно жестокому Петру Зиновьеву. Он определил Атласова на борьбу с неплательщиками ясака и самогонщиками. Тот взялся за дело настолько ретиво, что вскоре население засыпало воеводу жалобами на его ставленника. Уж слишком усердно бил он посуду у жителей Якутска. Перестарался Атласов и со сбором ясака: он и его помощники силой забирали меха у якутов и били их. В деле, возбужденном на основании жалоб против Атласова и другого казака, Мишки Гребенщикова, написано: «…они ездили в волости, воровали ясачных людей, разоряли, грабили и обиды им чинили». В то же время все свидетели единодушно признавали, что действовал сборщик не ради личного обогащения, а для покрытия недоимок в сборе ясака. Однако дело замять не удалось: по приказу воеводы Атласов был подвергнут обычному для той эпохи публичному наказанию – порот «на козле».
В 1691 г. Атласова отправили с глаз долой на Анадырь. Под началом приказного, боярского сына Семена Чернышева, он участвовал в походе против восточных чукчей, незадолго до того вероломно, во время сна, убивших анадырского приказного Василия Кузнецова. Виновников найти не удалось; к тому же Атласов начал конфликтовать с начальником, публично «срамил всякою неподобною бранью, матерной и ротовой, и вором и плутом называл». Дошло до того, что он обвинил приказного в государственной измене, а на дознании показал, что говорил это сгоряча и никакого «дела» за Чернышевым не знает. За это ему опять пришлось подставить спину под батоги, а потом ехать в Якутск. Его бывший начальник, вероятно, надеялся на то, что в столице края строптивого казака накажут дополнительно.
Однако по дороге в Якутск Атласов встретил давнего друга Андрея Ципандина, ехавшего в Анадырь сменить проштрафившегося Чернышева, и решил вернуться. По обычаю тех времен он договорился с одним из казаков об обмене службами. Однако вскоре взамен Ципандина на Анадырь прислали знаменитого Федора Пущина, за доблесть возведенного в высший казачий чин сына боярского. С новым начальником у Атласова установились вполне нормальные отношения. По приказу Пущина он вместе с отрядом казаков отправился в Якутск, чтобы привезти собранный ясак, и там впервые обратился к новому воеводе И. М. Гагарину с идеей об организации походов для изучения «новых землиц».
Гагарину Атласов понравился. Он произвел Владимира в пятидесятники и отправил собирать ясак в Борогонскую волость, а через год сделал его приказным Анадырского острога. До места службы новый приказный добрался только в 1696 г. и сразу начал собираться в поход на Камчатку.
Целый год готовили оружие, боеприпасы, продовольствие, инструменты и т. п. А в начале 1697 г. отряд из 65 русских казаков и 60 носильщиков-юкагиров выступил в поход. Маршрут проходил от устья р. Пенжины, впадающей в залив между Камчаткой и материком, через Камчатские горы, а затем вдоль обоих побережий.