Село первоначально населено было в 1778 г. отставными солдатами, семейства которых доставлялись на счет казны из разных губерний России. Женский пол впоследствии пополнялся ссыльными также из внутренних губерний. Потом переселенцы постепенно стали приписываться и составили общество, а в 1840 и 1844 годах село увеличилось вызванными из внутренних губерний крестьянами, преимущественно из Воронежской губ. Наконец в 1871—1875 годах были причислены к селу из соседних деревень Столыпинки и Петровки (Найденовка тоже) бывшие временно-обязанные крестьяне помещиков Шане-Гирея, Золотаревой и Хабановой. Число поселенцев, которыми было основано село, неизвестно, но в 1786 г. при сооружении церкви было 232 двора и считалось 513 душ м. п. и 244 ж. п. По первоначальным основателям села последнее и было названо «Солдатским», а когда была построена церковь во имя св. Александра-Невского, то оно стало называться «Солдатско-Александровским». Земли, занятые теперь селом, по существующему у жителей преданию, принадлежали князю Потемкину.
Александро-Невская церковь построена в 1786 году по благословению Антония, архиепископа Астраханского. В 1863 году церковь была перстроена. Здание деревянное, крепкое. Состав причта: 2 священника, 1 диакон и 2 псаломщика. Кружечный доход в 1909 году — 4130 руб. (клир. вед.). Казенного жалования положено: двум священникам по 137 р. 20 коп., диакону 68 руб. 60 коп. и первому псаломщику 45 р. Причтовой земли 132 десятины; арендуется по 5 руб. за десятину. Капиталов причта 2650 руб., в том числе по завещанию священника Иоанна Небовидова 1900 р. Церковно-приходская школа 1, помещается в собственном удовлетворительном здании. Министерских одноклассных училищ 2; жалованье законоучителю по 60 руб. от каждого училища. Население (ц. д.): православных 7065, раскольников-поповцев 36, баптистов 54, а всего 7155. Население (ст. ком.): 8180. Рождений 571, браков 84, смертей 259.
http://www.okorneva.ru/naselennyie-punktyi-stavropolskoy-gubernii-i-kubanskoy-oblasti/soldatsko-aleksandrovskoe-selo-praskoveyskiy-uezd/
10 сентября 2016 года по благословению епископа Георгиевского и Прасковейского Гедеона благочинный Зеленокумского округа протоиерей Роман Квитченко и протоиерей Виктор Самарин совершили освящение двух накупольных крестов строящегося в селе Солдато-Александровском нового храма в честь святого благоверного великого князя Александра Невского.
http://www.georg-eparhia.ru/2685-na-novyy-hram-sela-soldato-aleksandrovskogo-ustanovleny-dva-kupola-s-krestami.html