Первое письменное упоминание о роде Столыпиных относится ко времени царствования Иоанна IV (более известного в истории как Иван Грозный), когда некий тверской дворянин «Второй Титович Столыпин» «подписался на поручной записи (письменное поручительство за кого-либо в том, что это лицо в назначенный срок «на суд станет». –
Стоит хотя бы коротко сказать о некоторых наиболее выдающихся предках будущего премьера, и отнюдь не потому, что авторы придают излишне большое значение генеалогии и преувеличивают роль наследственности. Дело в том, что сам Петр Аркадьевич всегда помнил о своих служивых предках, гордился их заслугами перед Отечеством, и его становление в качестве государственного деятеля во многом обусловлено именно упомянутым фактором.
Документы о службе Столыпиных царю и Отечеству начинаются с внука уже упоминавшегося Григория Столыпина – Сильвестра Афанасьевича Столыпина, дворянина из города Мурома (откуда родом и причисленный к лику святых богатырь Илья Муромец, мощи которого покоятся в Киево-Печерской лавре), который принимал участие в войне с Польшей 1654–1656 годов. В 1672 году Сильвестр был пожалован в московские дворяне и получил грамоту на вотчину в 140 четвертей из 700 четвертей поместного оклада в Муромском уезде.
И после него все Столыпины служили Отчизне на военной или иной государевой службе, что уже подтверждается многочисленными документами.
Дед по матери Петра Аркадьевича генерал от артиллерии генерал-адъютант Михаил Дмитриевич Горчаков (1793–1861) – одна из наиболее заметных фигур в военной истории России. Он был участником Отечественной войны (в том числе Бородинской битвы), заграничных походов 1813–1814 годов (в том числе Битвы народов при Дрездене), польской войны 1831 года. Во время похода в Венгрию в 1849 году генерал Горчаков назначается начальником штаба действующей армии и проявляет незаурядные способности стратега. Во время Восточной (Крымской) войны 1853–1856 годов он сначала командует тремя пехотными корпусами, действовавшими на Дунае и побережье Черного моря до Буга, а после их вывода (по предательскому требованию австрийского императора Франца Иосифа I, оставшегося на троне только благодаря вводу в 1849 году российских войск в Венгрию) из пределов Валахии и Молдавии назначается командовать Южной армией на северо-западном побережье Черного моря и реке Прут. После высадки войск антироссийской коалиции в Крыму генерал некоторое время командует Крымской армией, а в феврале-августе 1855 года руководит обороной Севастополя. С января 1856 года Горчаков – наместник царства Польского и главнокомандующий 1-й армией. Согласно завещанию он был похоронен в Севастополе, героическая оборона которого была для генерала главным событием в наполненной сражениями и героизмом жизни.
Отец Петра Аркадьевича Аркадий Дмитриевич Столыпин (1822–1899) во многом повторил блестящую боевую биографию генерала Горчакова, также став генералом от артиллерии. Как офицер Генерального штаба он участвует в Венгерском походе и за боевые отличия досрочно получает капитанский чин, в Восточную войну сражается на Дунае и при обороне Севастополя (где получает золотую саблю с надписью «За храбрость»). Кстати, в Севастополе Аркадий Столыпин становится другом тогда еще неизвестного молодого офицера-артиллериста Льва Толстого и их закаленная в пороховом дыму дружба сохранится навсегда.