La première église orthodoxe à Ekaterinenshtadt, aujourd'hui connue sous le nom de ville de Marx, a été construite en 1838 au cimetière au début de la rue Ekaterininskaya et ressemblait à une maison en bois ordinaire. En 1848, une cloche et des maisons pour le prêtre et le diacre y ont été ajoutées. En 1867, la paroisse comptait 142 fidèles, et deux ans plus tard, leur nombre a dépassé 350 personnes.

Ekaterinenshtadt était la seule des colonies allemandes de la Volga où un temple orthodoxe a été construit, ce qui soulignait son importance parmi les autres colonies. Les fidèles étaient principalement des commerçants et des artisans.

Avec le temps, l'église en bois s'est détériorée, et il a été décidé de construire une nouvelle église en pierre. L'emplacement pour la construction a été choisi au même cimetière. Les fonds pour la construction ont été donnés par des commerçants russes, ainsi que par des Allemands, des catholiques et des luthériens. Pour chaque sac de blé expédié du port local, un kopeck en argent était prélevé pendant plusieurs années. Le 22 septembre 1874, l'évêque de Samara et de Stavropol, Hérésime, a consacré le nouveau temple, situé à l'emplacement de l'actuelle place Internationale dans le parc. Le temple avait deux autels : en l'honneur de l'Exaltation de la Sainte et Vivifiante Croix du Seigneur et de la sainte grande martyre Catherine.

En mai 1930, le temple a été détruit, et à sa place, un parc de culture et de loisirs a été aménagé. L'ancienne église en bois au cimetière n'a également pas survécu. Le supérieur, l'hiéromoine Vassili Marin, a été emmené dans une direction inconnue, et les services ont commencé à être célébrés dans les maisons des croyants. Lors du dernier service dans l'église de l'Exaltation de la Croix, le père Vassili a demandé aux fidèles de prendre les icônes sacrées. Prenant des risques, les croyants ont pu en sauver certaines. Deux icônes, celle du Sauveur et celle de l'archange Michel, sont conservées dans l'église moderne.

La paroisse Saint-André a été créée en 1989. Selon la décision du Conseil municipal de Marx du 15 août 1990, le bâtiment a été transféré gratuitement à la communauté orthodoxe pour en faire un temple. Le 13 décembre 1990, avec la bénédiction de l'archevêque de Saratov et de Volsk, Pimen Khmelevski, une réunion de la communauté a eu lieu, où il a été décidé de célébrer les offices dans la maison de la famille Sanayev sur la rue Rabochaya.

En 1996, la construction d'un nouveau temple en pierre a commencé. Cela a été aidé par l'administration municipale, des entreprises, des entrepreneurs et des habitants de la ville et de la région.

Le 25 novembre 2001, le prêtre Vassili Deev, avec le prêtre Vyacheslav Goloshchapov, a consacré le nouveau temple au nom du saint apôtre André le Premier appelé. Le 16 mai 2010, l'évêque de Saratov et de Volsk, Longin, a célébré la cérémonie de la grande consécration du temple.

Ces dernières années, le temple a été aménagé : un clocher et un dôme ont été installés, des cloches ont été acquises, des travaux de finition internes et externes à grande échelle ont été réalisés, et le territoire adjacent a été aménagé.