В мае 1900 года, после многочисленных рапортов, Арсеньев наконец был переведен из польского городка Ломжи, где он прослужил 4 года, в 1-й Владивостокский крепостной пехотный полк. Еще долгих 3 месяца ему пришлось добираться до северной части бухты Золотой Рог, где находился Владивосток.
Первое время Арсеньев часто ходил на охоту и увлеченно исследовал природу уссурийской тайги, затем вступил в Общество изучения Амурского края — филиал Русского географического общества, основанный в 1885 году. Но не одна лишь природа привлекала его пристальное внимание — он охотно общался с коренным населением и изучал его. Все свое свободное время Владимир Клавдиевич посвящал сбору редкой информации по истории, этнографии и природе края, первые же свои экспедиции по этим местам он совершал во время отпуска. Одна из них запомнилась Арсеньеву навсегда. Именно во время этой экспедиции он встретил человека, забыть которого ему было уже не суждено. Вот описание, приведенное Арсеньевым в его знаменитой книге: «У нашего огня стоял пожилой человек невысокого роста, приземистый, с выпуклой грудью, несколько кривоногий. Его плоское лицо было покрыто загаром, а складки у глаз, на лбу и щеках красноречиво говорили, что ему лет около 50. Небольшие каштанового цвета редкие усы, редкая в несколько волосков борода, выдающиеся скулы у глаз изобличали в нем гольда».
Новый знакомый по имени Дерсу Узала (Дерчу из рода Очжал) произвел на Арсеньева столь сильное впечатление, что он предложил ему присоединиться к его спутникам. Предчувствие того, что этот опытный охотник, знающий тайгу, как самого себя, принесет экспедиции огромную пользу, не обмануло исследователя. Впоследствии он писал: «Путешествуя с Дерсу и приглядываясь к его приемам, я неоднократно поражался, до какой степени были развиты в нем эти способности. Гольд (нанаец) положительно читал следы, как книгу, и в строгой последовательности восстанавливал все события. Трудно перечислить все те услуги, которые этот человек оказал мне и моим спутникам. Не раз рискуя своей жизнью, он смело бросался на выручку погибающему, и многие обязаны ему жизнью, в том числе и я лично». Прошло несколько лет службы, прежде чем поражение в войне с Японией заставило российское правительство пересмотреть свои дальневосточные позиции.
В декабре 1905-го Арсеньев был переведен в Хабаровск, а спустя полгода в составе военной исследовательской партии он, ставший уже штабс-капитаном, отправился в первое свое путешествие по горным хребтам неизведанного и загадочного Сихотэ-Алиня. В те времена у этих гор существовало несколько разных наименований: русские именовали их Проходным Рубцом, китайцы называли их Сихота-Линь, или Перевал Западных больших рек.
Целью того похода был сбор подробного топографического материала, способного пригодиться армии в случае новой войны с Японией. Минуя горные проходы Сихотэ-Алиня, Арсеньев со спутниками добирался до побережья Японского моря, где находился Порт-Ольга.
В своем путевом дневнике Владимир Клавдиевич записывал и анализировал всю собранную экспедицией информацию как с промышленной, так и с военной точек зрения, систематизируя неоценимые сведения, которые могли бы иметь огромное значение для потенциальной колонизации этих земель. Он наносил на карты названия рек на двух языках: русском и китайском, отмечал особенности их течения, ширину и глубину. Возможно, именно благодаря выработанной за годы привычке вести подробный дневник Россия и обязана появлению в лице Арсеньева столь талантливого писателя. Очевидно, что обязанности, которые он исполнял по долгу службы, только способствовали тому, что он полюбил эти края навсегда. Горы Сихотэ-Алиня стали для него тем местом, куда он не единожды возвращался с последующими экспедициями, каждый раз скрупулезно собирая все новые сведения и все более и более проникая в скрытые тайны здешней природы. Именно этим, любимым им местам он посвятил одну из своих книг — «В горах Сихотэ-Алиня», которая в 1937 году была опубликована впервые, уже 7 лет спустя после его смерти.
В той экспедиции Арсеньеву очень не хватало опыта и мудрости Дерсу Узала, а потому в следующую — в «сердце Зауссурийского края» — они отправились вместе. И пережить им пришлось немало: спасались от мошки, голодали, мерзли по ночам, спали под проливным дождем. А потому нелепая смерть друга от руки беглого каторжника на станции Корфовская весной 1908 года поразила Арсеньева в самое сердце. И этой потере суждено было в его жизни стать не единственной. Более того, она, по сути, открыла целую цепь трагических событий, которые в недалеком будущем принесли Арсеньеву немало горя, фатально преследуя его даже после смерти...