Piatra de temelie a bisericii a fost pusă în 21 noiembrie 2008, având la bază decizia Episcopiei Severinului și Strehaiei. Construcția a început în anul 2012.
Forma bisericii este una de cruce, fiind printre puținele lăcașuri de cult din oraș cu această arhitectură.
Andrei a fost un apostol al lui Iisus din Nazaret, frate cu Simon Petru. Evanghelia după Ioan menționează că Andrei ar fi fost mai întâi ucenic al lui Ioan Botezătorul, care i-ar fi recomandat să-l urmeze pe Iisus. Conform aceleiași evanghelii, Andrei l-ar fi dus pe fratele său Simon Petru la Iisus, spunându-i că l-a găsit pe Mesia. De aici provine caracterizarea lui Andrei ca „cel dintâi chemat”.
În enumerările apostolilor Andrei este menționat mereu între primii patru. Cu toate acestea, nu se numără printre cei trei pe care Iisus i-a tratat în anumite situații ca pe cei mai apropiați ai săi (Petru, Iacob și Ioan).
Conform Evangheliei după Ioan cei doi frați, Simon Petru și Andrei, erau originari din Betsaida, localitate situată pe malul Lacului Genezaret. Conform Evangheliei după Marcu aveau o casă în Capernaum și erau de profesie pescari.
Numele Andrei provine din greaca veche, care era lingua franca a Vechiului Orient.
La Sinodul Apostolic care a avut loc în jurul anilor 49-50 d.Hr. la Ierusalim, apostolii s-au întâlnit și au tras la sorți pentru a decide unde va merge fiecare. În Tradiția Bisericii Apostolului Andrei i-a revenit Scytia (Dobrogea). Mai întâi, Andrei l-a însoțit pe fratele său (Apostolul Petru) prin Asia Mică, apoi a trecut în peninsula Balcanică prin teritoriul Turciei de azi, ajungând în Scytia, unde s-a oprit un timp. Apoi a continuat misiunea de propovăduire a evangheliei, ajungând până în sudul Rusiei de astăzi.
În jurul anului 350 împăratul Constanțiu al II-lea (fiul lui Constantin cel Mare) duce moaștele sfântului Andrei la Constantinopol si le așează în Biserica Apostolilor. Acestea se păstreaza întregi până în jurul anului 850, când împăratul bizantin Vasile I Macedoneanul cedează rugăminților locuitorilor din Patras si le înapoiază capul sfântului Andrei. În anul 1208, în timpul Cruciadei a patra, relicvele au ajuns la Amalfi, în apropiere de Napoli, fiind păstrate în domul San Andrea. În 1462 au fost duse la Roma, din cauza pericolului turcesc. În secolul al XV-lea papa Pius al II-lea a mutat relicvele sfântului Andrei în Catedrala Sfântul Petru din Roma. În anul 1964 capul sfântului Andrei a fost înapoiat bisericii din Patras.
Este patron al Scoției (steagul scoțian reprezintă crucea sfântului Andrei), al României, al Spaniei, al Siciliei, al Greciei și al Rusiei. De asemenea, este patronul orașelor Napoli, Ravenna, Brescia, Amalfi, Mantua, Bordeaux, Brugge, Patras etc.
În România este socotit cel care a propovăduit Evanghelia pe aceste meleaguri. Mărturie stau toponimele din zona Dobrogei unde a și locuit o vreme. Peștera Sfântului Andrei, Paraiașul Sfântului Andrei sunt tot atâtea mărturii care dovedesc trecerea Apostolului pe aceste meleaguri.
