Село Столыпино было основано у реки Алай русскими крестьянами в начале ХVII века. Через село проходил тракт из Донгуза в Петровск. Названо поселение было по фамилии землевладельцев – древнего дворянского рода Столыпиных. Известно также другое дореволюционное название села – Дмитриевское, являвшееся до второй половины XIX века основным (возможно, в честь помещика Дмитрия Алексеевича Столыпина или по приделам сельского храма).
В 1801 году была построена первая церковь. Храм был деревянным, с колокольней и тремя престолами: центральный в честь Рождества Пресвятой Богородицы, правый в честь святителя Дмитрия Ростовского и левый в честь святого великомученика Димитрия Солунского. В штате причта состояли священник и псаломщик, проживавшие в церковных домах. В конце XIX века при храме открылась приходская школа. В 1930 году село было переименовано в Калинино. Местная церковь была закрыта, а впоследствии разрушена.
В 1996 году селу было возвращено старое название – Столыпино. Храм был заложен 8 ноября 1994 года и построен тщанием губернатора Саратовской области Д.Ф. Аяцкова по проекту саратовского архитектора Д.В. Голубинова в 1996 году. Роспись интерьера церкви выполнена под руководством А.Г. Моченцова.