Как известно, честь начала беспощадной борьбы с террором, борьбы, в которой, как он считал, все средства были пригодны, принадлежит премьер-министру Петру Аркадьевичу Столыпину. «Сначала успокоение, потом — реформы, — говорил Столыпин и добавлял: — Им нужны великие потрясения, нам нужна великая Россия». По стране прокатилась волна политических арестов. Тысячи осуждены на смертную казнь, сотни тысяч отправлены в тюрьмы и ссылки. Как только Столыпина в России ни называли: «Столыпин-палач», «Столыпин-вешатель» и «Столыпин-душитель» — не единственные его прозвища. В российском фольклоре появились такие понятия, как «столыпинский вагон» — специальные пульмановские железнодорожные вагоны для перевозки заключённых, — и «столыпинский галстук» — выражение, означающее виселицу. Это крылатое словосочетание родилось в недрах Государственной думы, во время яростной полемики вокруг внутриполитического курса правительства Столыпина. Оно принадлежит депутату от партии кадетов Фёдору Измайловичу Родичеву. Столыпин, которого не без оснований часто называли «Последним дворянином» (известно, что дальними родственниками Столыпина были М. Ю. Лермонтов и А. М. Горчаков), защищая свою дворянскую честь, вызвал Родичева на дуэль. Дуэль не состоялась. Родичев извинился, Столыпин принял извинения, и инцидент был исчерпан, но «эффектная идиоматическая липучка» «столыпинский галстук» прилипла к мундиру Петра Аркадьевича навеки.
Хорошо известно, что политика усмирения террора вызвала волну ненависти лично к Столыпину. На него совершили одиннадцать покушений. Последнее, закончившееся трагической смертью премьер-министра, произошло в Киеве 1 сентября 1911 года. Свою смерть Столыпин предчувствовал. В тот трагический день в Киеве будто бы находился Григорий Распутин. Когда Столыпин случайно его увидел, тот «в экстазе завопил»: «Смерть за ним! Смерть за ним!» (если, конечно, верить фольклору).
В связи с этим вспоминается август 1906 года, когда от одного из очередных покушений в доме на Аптекарском острове в Петербурге серьёзно пострадала дочь Петра Аркадьевича — Наталья. Ранение оказалось таким тяжёлым, что врачи настаивали на ампутации обеих ног. Столыпин не соглашался, настаивал на лечении, и врачи в конце концов спасли обе ноги. Но перед этим Наталью, будто бы по настоянию императора Николая II, посетил Распутин, совершил над её головой несколько пассов, пробормотал молитву и со словами «Скоро пойдёт» выбежал из дома. Столыпин догнал его и со слезами на глазах поблагодарил. Распутин пристально посмотрел на него и сказал: «Ты хороший человек. Но убьют тебя. И меня за тобой». Тогда молва приписала выздоровление Натальи Распутину.
И ещё. Столыпин ненавидел Распутина, считая его едва ли не единственным источником дурного влияния на царскую семью. Он добился решения правительства о высылке Распутина из Петербурга и лично объявил ему об этом. «Ладно, — будто бы покорно ответил Распутин. — Уеду. Не хочу видеть, как тебя убьют».
В фольклоре сохранились две легенды о неудавшихся покушениях на Столыпина в Петербурге. Обе связаны с модными в то время испытательными полётами авиаторов на Комендантском аэродроме. Однажды Столыпин вместе с другими членами правительства присутствовал на авиационных испытаниях. Один из авиаторов обратился к нему с предложением полетать вместе с ним. Ни минуты не колеблясь, Столыпин принял предложение и более получаса провёл в воздухе. А когда самолёт приземлился, Столыпину доложили, что полиция обладает сведениями, полученными за несколько дней до этого. Оказывается, он летал с лётчиком, который принадлежал к одной из наиболее опасных террористических организаций. Но самое удивительное заключалось в том, что и Столыпин был осведомлён об этом, когда «согласился подняться в воздух».
Другой случай несостоявшегося теракта произошёл на Комендантском аэродроме в 1910 году. Он совпал с трагической гибелью одного из первых русских лётчиков Льва Мациевича. Мациевич погиб на глазах тысяч зрителей во время всероссийского праздника воздухоплавания. Пилотируемый им аэроплан потерпел аварию. Между тем говорили, что Мациевичу как члену партии эсеров дали задание исполнить роль «камикадзе» — убить премьер-министра П. А. Столыпина и погибнуть самому. Мациевич отказался выполнить это задание, и товарищи по партии тайком повредили ему самолёт, который и «сломался в воздухе». По другой версии той же легенды, Мациевич сам покончил с собой после того, как по каким-то причинам не смог выполнить задание партии.