Село Стрельцы берет свое начало от Стрелецкой слободы, образованной в период строительства Тамбовской крепости в 1636 году. Слобода была заселена служилыми людьми — стрельцами, которые обрабатывали земли в окрестностях крепости. В результате выселения стрельцов из Тамбова в 1830-х годах было основано село Стрельцы.
Инициатива строительства новой церкви в селе принадлежала местным жителям, которые пожертвовали средства на сооружение храма. В 1901 году каменная церковь во имя преподобного Сергия Радонежского была освящена. Храм имел два престола: главный — в честь Сергия Радонежского и придельный — в честь иконы Божией Матери "Знамение". Приход был открыт в том же году.
Архитектурно церковь выполнена в стиле русской эклектики. Композиция храма включает высокий четверик, несущий световой восьмерик, завершенный рядом кокошников у основания шатра и луковичной главкой на граненой шее. С востока к основному объему примыкают три граненые апсиды, с запада — небольшая трапезная и четырехъярусная шатровая колокольня с луковичным венчанием. Фасады украшены декоративными элементами, характерными для данного стиля.
В советский период, несмотря на официальное непрекращение деятельности, здание храма использовалось не по назначению. В частности, в 1933–1943 годах в нем размещался зерносклад. В 1990 году церковь была возвращена верующим, после чего начались восстановительные работы. В 1990-х годах рядом с храмом была сооружена небольшая металлическая водосвятная часовня.