Первым браком Аркадий Столыпин был женат на Екатерине Устиновой. О его супруге мало известно. Можно отметить только, что между родом Устиновых и Столыпиными несколько раз заключались браки. Супруга родила ему сына Дмитрия и скончалась при родах или после родов. Вероятно, с этим печальным уходом было связано прошение Аркадия Столыпина об увольнении с военной службы в апреле 1848 г. Основанием была названа болезнь, но это скорее всего формальная причина, так как в июне 1849 г. он по его просьбе вновь был определен на службу в конную артиллерию.
За время недолгой отставки Столыпина по Европе прокатилась волна революций. В лоскутной Австрийской империи вспыхнуло Венгерское восстание. Поскольку в Николаевскую эпоху Россия играла роль «жандарма Европы», император взялся спасти династию Габсбургов. Аркадий Столыпин никоим образом не сочувствовал революциям, потрясшим европейские монархии. Он был в армии, которая под командованием фельдмаршала Ивана Паскевича перешла через Карпатские горы. Сохранился рассказ о том, что во время похода он навлек на себя гнев фельдмаршала своим щегольским моноклем. В послужном списке Столыпина сказано: «В войну с венгерскими мятежниками… находился за офицера Генерального штаба при начальнике летучего отряда артиллерии полковника Хрулева».
Степан Хрулев командовал летучим отрядом, действовавшим в тылу инсургентов. Отряд подвергался постоянной опасности, из которой выручала только хладнокровие и находчивость командира. Однажды отряд наткнулся на венгерский корпус Шандора Надя. Положение казалось безнадежным, но Хрулев пошел ва-банк, потребовав от повстанцев немедленной капитуляции. Повстанцы решили, что окружены, запросили через парламентариев двухдневное перемирие, а за это время подошли основные силы Паскевича, и отряд был спасен. В послужном списке Столыпина отмечено, что он «был в перестрелках с венгерцами». Он зарекомендовал себя образцовым офицером и был награжден серебряной медалью «За усмирение Венгрии и Трансильвании» и получил повышение в чине.
Император Николай I надеялся, что Австрийская империя, которую он спас от развала, окажет помощь в войне с Турцией, начавшейся в 1853 г. и получившей название Крымской войны. Император просчитался, и в этом военном конфликте Россия оказалась в одиночестве против англо-франко-турецко-сардинской коалиции при враждебном нейтралитете Австрии и Пруссии. Аркадий Столыпин участвовал в Крымской войне с первых ее дней, сначала на Дунайском театре военных действий, а после высадки союзников в Крыму был переведен в Севастополь. Оборона Севастополя является одной из самых героических страниц истории русской армии и флота. Вместе с тем Севастопольская оборона, продемонстрировав мужество защитников города, показала техническую отсталость русских вооруженных сил. Аркадий Столыпин, командовавший артиллерийской батареей, имел в своем распоряжении практически такие же пушки, которые отбивал у французов его отец Дмитрий Столыпин во время Аустерлицкого сражения. Их заряжали с дула, тогда как противник располагал современными нарезными орудиями, заряжавшимися с казенной части. И конечно, всех защитников Севастополя приводили в ярость разговоры о повальном воровстве в тылу, об интендантах с набитыми ассигнациями карманами, о бессовестных военных поставщиках, наживавших миллионы на страданиях солдат и матросов.
