В январе 1896 года Арсеньев закончил училище и только теперь узнал, что своекоштных юнкеров решено посылать в армию. Подпоручик Арсеньев был направлен в 14-й пехотный Олонецкий полк, стоявший в польском городе Лонжа. Но и здесь его не оставляли мечты о путешествиях и прежде всего путешествиях по Сибири и Уссурийскому краю, некогда описанному Пржевальским. Арсеньев упорно добивается своего перевода на Дальний Восток, и после нескольких отказов его просьба была удовлетворена.
Именно здесь он научился сочетать военную службу с походами по тайге, в которых он набирался того опыта, который пригодился ему как руководителю будущих экспедиций.
В январе 1903 года Арсеньев был назначен начальником Владивостокской Крепостной конно-охотничьей команды. В задачу таких команд входило обследование дальневосточного края в военно-географическом отношении и собирание статистических данных стратегического характера. Во многом работы этих команд не отличались от экспедиций Географического общества. Таким образом, Арсеньев набиравшийся опыта, расширял пределы своих таежных исследований.
В начале русско-японской войны 1904–1905 годов Арсеньев руководил военной разведкой Владивостокской крепости. За умелое руководство он был награжден тремя боевыми орденами. В декабре 1905 года Арсеньев был переведен в штаб Приморского военного округа, находящийся в Хабаровске.
На следующий год, в мае 1906-го, Арсеньев возглавил свою первую экспедицию в горы Сихотэ-Алиня. Программа экспедиции была разработана штабом Приморского округа, и на Арсеньева как на руководителя экспедиции легло множество обязанностей, вплоть до ежедневных хозяйственных распоряжений.
В экспедиции Арсеньев неутомимо каждый день вел дневники, в которые он заносил не только свои наблюдения за жизнью Уссурийского края, но и свои личные переживания.
В этой же экспедиции на одном из биваков 9 августа 1906 года к Арсеньеву пришел охотник — гольд по имени Дерсу, ставший проводником его отряда. Наверное, и сам Арсеньев не подозревал тогда, что в будущем Дерсу Узала станет главным героем его книги.
Экспедиция 1906 года продолжалась 180 суток. За время этой экспедиции Сихотэ-Алинь был преодолен в нескольких местах.
Впечатления от увиденного воплотились в книге «По Уссурийскому краю», написанной на основе дневников, которые велись в ходе экспедиции.
В 1908–1910 годах Арсеньев возглавил новую экспедицию. Она проходила на севере Уссурийского края и стала для него одной из самых трудных в жизни. Отряд Арсеньева шел через дике, безлюдные районы с суровым климатом. Переходы были крайне утомительны, поскольку отряд шел без всяких троп. На стремительных горных речках переворачивались лодки. Иногда в отряде ощущалась острая нехватка продовольствия. Многие участники экспедиции вынуждены были покинуть отряд, и на заключительном этапе экспедиции Арсеньев остался лишь с двумя стрелками. Началась суровая зима, морозы доходили до 40 градусов. Арсеньев и его спутники 76 дней шли на лыжах и сами на себе тащили нарты с коллекциями, поскольку собаки погибли от голода. На привалах участники экспедиции ночевали в рваной палатке, заносимой снегом.
Чудом им удалось добраться до человеческого жилья, спасти свои жизни и собранные коллекции.
По возвращении из экспедиции Арсеньев отправился в Петербург. Здесь он на заседании Русского Географического общества сделал несколько блестящих докладов, привлекших внимание и известных русских ученых, и широкие круги общественной публики.
За богатейшие коллекции, пожертвованные на Общероссийскую этнографическую выставку, Арсеньев был награжден большой серебряной медалью, а за экспедиционную деятельность получил малую серебряную медаль Географического общества.
Хабаровский краеведческий музей избрал его своим директором, и теперь Арсеньев мог свободно посвятить себя науке. Немалую роль в этом сыграло и высочайшее повеление о том, что «в изъятии из закона» Арсеньев освобождается от службы в войсках и штабах и, сохраняя воинское звание и чинопроизводство, переводится в Главное управление землеустройства и земледелия. Теперь он становится личностью достаточно известной как на Дальнем Востоке, так и в столице.
Он постепенно становится не только знаменитым ученым-исследователем Уссурийского края, но и популярным писателем.
Уже после экспедиции 1908–1910 годов Арсеньев решил написать книгу под названием «По Уссурийскому краю». По замыслу Арсеньева ее первая часть должна была носить научно-литературный характер. В эту часть должно было войти все, что так или иначе связано с самим путешествием. Вторую же должны были составить чисто научные материалы, которые Арсеньев намеревался обработать с помощью различных специалистов.