Село Елховка, основанное в 1745 г. на землях капитана Петрова, своим названием обязано близлежащему оврагу, впадающему в русло реки Кондурча. Елховка изначально была крупным селом, а также волостным, а позднее районным центром. В народе её называли Покровской Елховкой по имени первого храма Покрова Святой Богородицы, построенного в 1807 г. Небольшая церковь вмещала 300 прихожан. В конце XIX в. храм уже не мог вмещать всех желающих, поэтому 19.02.1895 на очередном сходе открытым голосованием 424 домохозяев, имеющих право голоса в приходских делах, было решено построить в селе новый храм во имя Святой Троицы и «собирать с имеемых в приходе 923 ревизских душ по 1 рублю с начала 1895 г. по окончании всей работы».

Автором проекта перестройки зернового хранилища под здание храма выступил известный самарский архитектор А.А. Щербачёв. Новая каменная холодная церковь с деревянным куполом и каменной колокольней вмещала около тысячи прихожан. Около храма была выстроена деревянная сторожка. Строительство было завершено в 1904 г., а в следующем году уже освятили престол в честь Святой Троицы. Причта храму не полагалось, службы проводили священники Покровской церкви.

В клировых ведомостях 1911 г. упоминается второй престол в честь Святителя Николая Чудотворца. Вскоре храм был закрыт и переоборудован под клуб и кинотеатр. Верующим он был возвращён в 1991 г. В настоящее время храм восстанавливается силами прихожан и настоятеля.