Путешествие началось на станции Шмаковка 20 мая 1906 г. Сначала отряд поднялся по течению Уссури до слияния питающих ее рек Дауби и Улахэ. Отсюда начался трудный подъем к вершинам Сихотэ-Алиня. Несмотря на тяжесть похода, партия благополучно нашла путь через перевал и, преодолев хребет, оказалась на его восточных склонах. Изучив систему рек Фудзин, Лифудзин и Вайфудзин, отряд вышел к заливу Святой Ольги. Исследования продолжались все лето. Отряд то двигался по берегу моря, то углублялся в таежные дебри, то поднимался к горным перевалам, то спускался в речные долины. На пути разведчиков то и дело попадались китайские деревни и отдельные фанзы, обитатели которых порой встречали партию если и не враждебно, то настороженно.
Много позже, в начале 1910-х гг., Арсеньев вспоминал, что обстановка в таежной глубинке края в 1906–1907 гг. была очень беспокойной. Поражения в Маньчжурии дискредитировали русских в глазах «манз», вновь зародивших надежду установить в Приморье «китайскую власть». Уже в годы войны любая новость с фронта лихорадочно обсуждалась китайцами, забросившими все свои работы и толковавшими только об одном — где добыть оружие и патроны. Последние не заставили себя ждать, и вскоре вместо старых берданок и винчестеров в руках «манз» оказались современные армейские трехлинейки. Винтовки в разобранном виде попадали в край на борту китайских джонок, к тому же известную долю «урожая» нелегальных стволов дали беспорядки, то затухавшие, то вновь разгоравшиеся в войсках Владивостокского гарнизона на протяжении 1905–1907 гг. На Даубихэ, Сучане и Имане все китайское население было вооружено. Ощущение силы делало поведение «манз» в отношении экспедиции «смелым, чтобы не сказать дерзким».
Вскоре Арсеньеву стало известно, что китайцы производят по пути следования экспедиции «розыски», выявляя и наказывая «инородцев», указывавших отряду путь в лесных дебрях. Перед Арсеньевым стояла мрачная перспектива лишиться проводников. Можно представить себе радость исследователя, когда 3 августа к отряду присоединился его старый знакомый — нанаец (гольд) Дерсу из рода Узала (или Оджала), знакомый Арсеньеву со времен «экскурсий» 1902 г. Прекрасный следопыт и знаток тайги, Дерсу уже в юные годы совершил настоящий подвиг, угодив в плен к шайке хунхузов и сумев уйти невредимым. Во время совместных путешествий гольд неоднократно помогал Арсеньеву избежать опасных встреч на таежных тропах.
Ко времени появления Дерсу отряд Арсеньева уже больше месяца занимался обследованием побережья в окрестностях залива Святой Ольги. Теперь его присутствие было особенно кстати, так как экспедиции предстояло, вновь перевалив Сихотэ-Алинь, выйти в бассейн реки Ното, почитавшийся самым глухим и опасным уголком Уссурийского края, привлекавшим подонков «манзовского» общества. Здесь русская власть не имела никакой силы, в чем Арсеньев и его спутники смогли убедиться уже на подходе к хребту. Близ фанзы Иолайза на реке Фудзин отряд ожидала страшная находка — могилы китайца и молодого таза, погребенных заживо всего лишь за двое суток до появления разведчиков. Несмотря на свой чин, начальник партии не мог принять никаких мер к самозваным «судьям» — слишком велико было численное превосходство китайцев. Случай «применить власть» представился путешественнику 12 августа, уже к западу от гор, на реке Вангоу: казаки Арсеньева заставили китайских зверовщиков засыпать заброшенные ловчие ямы, попусту губившие животных.
21 сентября произошло событие, ставшее самым опасным приключением экспедиции: неподалеку от залива Пластун отряд едва не столкнулся с шайкой из двух десятков хунхузов. Путешественников спас от нежелательной встречи Дерсу, от зоркого глаза которого не укрылись следы, оставленные «краснобородыми» на тропе. Окурок редкой для тайги папиросы, лоскут ткани, который китаец рабочий никогда не выбросил бы, — все эти детали насторожили гольда, немедленно вызвавшегося идти на разведку. Дерсу удалось выследить разбойников и благополучно вернуться, отделавшись простреленной одеждой. По совету охотника экспедиция покинула тропу и укрылась в лесной чаще.