По окончании в 1855 году Императорского училища правоведения, одного из наиболее престижных высших учебных заведений дореволюционной России, Арсеньев поступил на службу в Министерство юстиции (в 1859–1860 годах он был помощником редактора «Журнала Министерства юстиции»). «Кто был молод сорок, тридцать лет тому назад, тот, вероятно, помнит, какую роль играли тогда сочинения Гизо, Минье, Огюстена, Тьерри, Баранта, Мишле, Нибура, Шлоссера, Ранке, Гервинуса, Грота, Сисмонди, Маколея, нашего Грановского или Кудрявцева, как много они способствовали самообразованию, пробуждению интереса к политической жизни, – вспоминал Арсеньев в 1890 году период своего личностного и гражданского становления. – Многие из этих авторов не утратили своего значения и теперь, и к ним присоединилась масса других, из которых достаточно назвать сочинения Леки, Тэна, Ренана, Буассье, Сореля, Зибеля, Моммзена, Дункера, Курциуса, Трейтшке, Гаусрата, Костомарова, Соловьева».
Поставив целью подготовку к профессуре, Арсеньев усиленно занимался древними языками, посещал лекции М.М. Стасюлевича (1826–1911) по истории в Петербургском университете. Тогда же вкус к литературным занятиям и стремление делиться мыслями с широкой аудиторией привели Арсеньева в публицистику. Его дебют на этом поприще состоялся в журнале «Экономический показатель» (1857, выпуск 21). Затем последовало сотрудничество в «Русском вестнике» и «Веке» (1858–1861) и далее – в «Отечественных записках» (в марте-октябре 1862 года – ведущий раздела «Иностранное обозрение») и «Санкт-Петербургских ведомостях» (с июня 1863 до весны 1864 года – зав. иностранным отделом), где молодой автор продемонстрировал широкую эрудицию и глубокий анализ политических проблем современности. В двух последних изданиях судьба вновь свела Арсеньева со Стасюлевичем. С 1866 года их пути сольются – уже до конца жизни – в одну «колею», которую они будут прокладывать в русском либерализме как отцы-основатели журнала «Вестник Европы» (1866–1918), а с 1906 года – как зачинатели либерально-центристского (условно, между кадетами и октябристами) течения в российской партийной системе.
Несмотря на сохранявшийся у Арсеньева вплоть до середины 1860-х годов настрой на серьезные занятия наукой (в 1864–1865 годах он слушал лекции по философии, истории и политической экономии в Боннском университете, посещал занятия в семинаре Г. фон Зибеля – автора 10-томной «Истории революционной эпохи. 1848–1849»), он в конце концов отказался от профессорской карьеры. Сыграло роль его стремление посвятить знания и энергию коренному преобразованию российской правовой системы, оформившееся в атмосфере предчувствия Великих реформ Александра II и под влиянием еще одной судьбоносной встречи, состоявшейся в 1858 году, – с Д.В. Стасовым (1828–1918). Представитель прославленного семейства, члены которого внесли значимый вклад в русскую культуру и развитие общественного движения, Стасов по окончании Училища правоведения (1847) служил чиновником Герольдии Правительствующего сената, в качестве герольда летом 1856 года участвовал в короновании Александра II, был пожалован бриллиантовым перстнем с рубином. С 1858 года он занимал должность обер-секретаря Гражданского департамента Сената. В 1859 году Стасов организовал в Петербурге один из первых юридических кружков, целью которого было «приготовление к судебной реформе». Заседания кружка, обычно проходившие в его доме, привлекали внимание не только юристов, но и известных ученых, художников, литераторов. Среди завсегдатаев этих собраний был и Арсеньев. Начинающего юриста не устраивала служебная карьера сама по себе, в рамках давно сложившихся «правил игры». Главное место в системе его жизненных ценностей уже тогда прочно занимали идеи законоправия, просвещения и свободы.