Stavba původně románské baziliky proběhla někdy ve 20. letech 13. století. Záhy však došlo k požáru a zničené části byly rekonstruovány již v gotickém stylu. Během staletí bylo realizováno ještě několik dalších stavebních úprav v duchu baroka a novogotiky. Poslední rekonstrukce (2008) “vrátila” kostelu dvě vysoké jehlancové věže, o které přišel v roce 1945 při útoku spojeneckých stíhacích letounů.


První stavbu kostela tvořila trojlodní románská bazilika o čtyřech polích s vázaným klenebním systémem. Na východní straně byl čtvercový chór s dvojicí věží, západní stranu kostela uzavírala příčná loď s hlavním portálem. Zde nalezené základy věží ukazují na původní záměr výstavby dalších dvou západních věží, které potvrzují souvislost chebské stavby s dokončenou stavbou chóru bamberského dómu v roce 1218. Z původní románské stavby se zachovala spodní tři patra věží, západní portál a části severního portálu. Ve vnější zdi bývalé severní předsíně zazděné, drobné románské plastiky, které daly vstupu název brána "sedmi bratří", pocházejí s fasády věží a byly sem patrně vsazeny až při pozdně gotické přestavbě kostela.


K první přestavbě původní baziliky už dochází po velkém požáru v roce 1270, kdy byla poškozená románská část nahrazena novým gotickým chórem a k severní stěně pak později přistavěna sakristie. Především nadace Sigmunda Wanna, bohatého chebského měštana a zakladatele kostela a špitálu v rodném Wunsiedlu, určená chebskému farnímu kostelu, vedla město k velkorysé přestavbě chrámové lodi v 2. polovině 15. století. Do nové, 50 m dlouhé a 30 m široké, trojlodní haly je převzata původní střední loď mezi západním románským portálem a východním raně gotickým chórem, neboť svou délkou vyhovovala záměrům přestavby. Obě boční lodě, které byly o polovinu užší, byly rozebrány a dvojnásobně rozšířeny při zachování výšky střední lodě.


Do roku 1470 byla pod vedením mistra Jorgena z Chebu dokončena klenba a v roce 1472 je povolán z bavorského Eichstättu kameník Erhard Pauer, který dokončuje stavbu lodi v roce 1476. Z té doby máme zachovanou zprávu o malování klenby kostela mistrem Lukasem z Norimberka, ostatní malby na zdech a sloupech provedl Georg Eberhardt z Chebu. Tyto malby, v době baroka zabíleny a po restaurování částečně obnoveny, představují na sloupech postavy apoštolů, na zdech pak výjevy z Nového zákona. Z vnější malířské výzdoby víme o dvou freskových výjevech na fasádě. Postava sv. Krištofa byla odstraněna při opravě v letech 1890-94, další freska z počátku 17. století byla nahrazena malbami na plechu od F. Schilhabela (1874) a Antona Friedla (1928).


Rovněž z původního románského, gotického a později barokního vybavení kostela se po mnoha požárech a úpravách nedochovalo téměř nic. V Chebském muzeu je uložena velká stříbrná monstrance, norimberská práce z počátku 15. století, deskový obraz donátora Sigmunda Wanna, stejně jako bronzová klepadla s kruhovými držadly upevněnými do lvích masek, která byla jako cenná práce z doby kolem roku 1400 (patrně z norimberské dílny Vischerů) odstraněna koncem 19. století z vrat jižního portálu a předána do muzea. Kovový pozlacený lustr s postavami 12 apoštolů, který údajně věnovali kostelu při své cestě do Chebu v roce 1404 norimberští tovaryši cechu mědikovců, darovala městská rada v roce 1825 na vybavení císařského zámku v Laxenburgu. V kostele tak nacházíme pouze na obou bočních novogotických oltářích z roku 1863 šest pozdně gotických dřevěných plastik světců z počátku 16. století a v severní zdi chóru pískovcový sanktuář z konce 14. století se znaky rodu Bachmannů.


Z barokního vybavení kostela, které bylo z větší části zničeno požárem, se dochovalo 15 pašijových obrazů z poloviny 17.století (patrně od malíře Georga Adama Eberharda), kovové mříže kolem křtitelnice (kolem 1700) od chebského uměleckého kováře Georga Herbecka a mříže u vchodu v západní části od Andrease Herbecka z roku 1720. Obraz na jižní stěně, zachycující procesí sv. Vincence, od roku 1693 dalšího patrona města Chebu, byl zhotoven kolem roku 1740. Převážná část novogotického interiéru pochází z druhé poloviny 19. století. Postranní oltář sv. Petra a Pavla a Mariánský oltář jsou práce pražského sochaře Heidlberga a mnichovského malíře Kökerta z let 1862-64, hlavní novogotický oltář a kazatelna byly zhotoveny v letech 1890-94. Z této doby také pochází přestavba západní předsíně s plastikami patronů sv. Alžběty a sv. Mikuláše. V roce 1894 pak byly instalovány mistrovské varhany z dílny Martina Zause s 2997 píšťalami.


Proměny vnější podoby střízlivé, bez větší výzdoby provedené kostelní stavby nejlépe dokládají dostavby kostelních věží. První gotické helmice s nárožními věžicemi byly na kostel osazeny po roce 1470. Po požáru v roce 1742 byl požádán chebský rodák Balthasar Neumann o zhotovení plánu nových věží. Dostavba nových věží od dochované výšky zvonice byla dokončena osazením dvojité barokní kopule na jižní věži, zatímco severní věž zůstala nedostavěna s provizorní pultovou střechou. Po požáru v roce 1809, kdy byly obě věže i loď kostela vážně poškozeny, byla dokončena pouze jižní věž a opatřena tentokrát neogotickou helmicí se čtyřmi nárožními věžičkami. Oprava severní věže, opět pouze nouzově zastřešené, byla dokončena až o padesát let později. Dnes zase čekají, tentokrát obě věže kostela poškozené v roce 1945, společně již více než dalších padesát let na své dokončení.