Первая однопрестольная православная церковь была построена в нашем городе в 1838 году на кладбище и имела вид обыкновенного деревянного дома. В 1848 г. к ней были пристроены колокольня и дома для священника и причетника. Если в 1867 г. приход состоял из 142 прихожан, то через два года их число превысило 350 человек.
Необходимо отметить, что из всех поволжских колоний в те годы только в Екатериненштадте был построен православный храм. Это говорит о центральном значении города среди колоний. Приход составляли в основном купцы и ремесленники, в их числе болгары и греки, небольшим числом проживавшие в колониях.
Со временем деревянная церковь стала ветшать. Решено было строить новую — каменную церковь. Средства на эти цели жертвовало русское купечество, а также немцы: католики и лютеране. С каждого мешка пшеницы, отправленного с Екатериненштадтской пристани, отчисляли по 1 копейке серебром, в течение нескольких лет. И вот 22 сентября 1874 г. новый храм был освящен, а находился он на месте нынешней Интернациональной площади в районе городского парка. Храм носил имя в честь Воздвижения Честного и Животворящего Креста Господня и Святой Екатерины.
Грянула октябрьская революция. В мае 1930 г. храм был разрушен. Не избежала этой участи и ветхая деревянная церковь на кладбище. Верующие сумели спасти некоторые иконы. Две из них: образа Спасителя и Архистратига Михаила — хранятся в нынешнем современном храме.
Свято-Андреевский приход был организован в 1989 году. Согласно решению Марксовского городского Совета народных депутатов от 15 августа 1990 года православной общине было безвозмездно передано здание под храм. Храм был освящен иерейским чином.
13 декабря 1990 г., по благословению архиепископа Пимена, состоялось собрание общины, и было принято решение проводить богослужение в жилом доме семьи Санаевых по ул. Рабочая. Через некоторое время верующим передали здание бывшей школы, обустроенной под домашнюю церковь. В 1996 г. началось строительство каменного храма. Содействие в этом оказывали городская администрация, а также многие предприятия, предприниматели, жители города и района.
25 ноября 2001 г. в служении настоятеля иерея В. Деева и священника В. Голощапова было совершено освещение нового храма во имя Святого Апостола Андрея Первозванного. При приходе действуют детская воскресная школа и православная библиотека.
По инициативе прихода установлено два поклонных креста: на въезде в г. Маркс со стороны г. Саратова и г. Балаково.
В 2007 году на приходе производились ремонтно-восстановительные работы: приобретены и установлены два колокола, реставрирован и установлен шатер колокольни, установлен новый купол на колокольне, изготовлен и установлен новый иконостас, произведен косметический ремонт внутри храма и фасада колокольни. В 2008 году ремонтные работы были продолжены.