Kostel sv. Mikuláše a sv. Alžběty stojí na Kostelním náměstí v severovýchodním rohu náměstí Jiřího z Poděbrad, kde jeho pozice na vyvýšeném místě činí jej dominantou této části Chebu. Jedná se o nejstarší existující kostel v městě a současně důležitou kulturní památku chráněnou od roku 1970.

Počátky stavby lze datovat předpokládáně do dvacátých let třináctého století, přestože přesné datum není známo. První písemná zmínka pochází až z roku 1239, kdy se zmiňuje zasvěcení oltáře svaté Anně. Spolu s kostelem byl založen i přilehlý hřbitov, který již dnes neexistuje. Románská bazilika původně nabízela trojlodní členění, které se v průběhu staletí zásadně proměnilo. Při velkém městském požáru v roce 1270 bylo zařízení těžce poškozeno a následné opravy přinesly gotické prvky – nový chór a sakristii.

Zásadní přeměna přišla v pozdním středověku. Od roku 1456 se měšťané Chebu shromažďovali na sbírkách na rozsáhlou přestavbu. Mezi věhlasnými podporovateli byli členové rodiny Junckerů a bohatý obchodník Sigmund Wann. V letech 1456 až 1470 vedl mistr Jörg z Chebu transformaci kostela na pozdně gotickou halu, inspirovanou amberským chrámem. Zdi bočních lodí byly rozebírány a zvýšeny, v létech 1472 až 1476 zhotovil nové klenby mistr E. Bauer z Eichstättu. Kostel získal nové vnitřní vybavení, nové malby a věže se vznesly do výšky s gotickými hlemicemi. Někdy po roce 1730 vzniklo severně od chrámu kamenné schodiště eliptického půdorysu se sochami svatého Jiřího, svatého Michaela a Panny Marie.

Osmnáctého století se neslo v duchu vojenských nepokoj a jejich následků. V roce 1742, kdy město obsadili Francouzi, zasáhl kostel blesk a obě věže vyhořely. Válečný chaos neumožnil okamžité opravy. Až v roce 1747 přivezli nové zvony a nastoupil k práci významný chebský architekt Balthasar Neumann, který vedl obnovu věží. Do roku 1758 byly věže vybaveny novými barokními hlemicemi cibulovitého tvaru. Další úpravy interiéru proběhly v roce 1790 s výměnou oltářů. Necelých dvacet let později, v roce 1809, příšel další požár, který zničil stovku budov. Kostelu sv. Mikuláše byly zničeny helmice, poškodil se oltář a interiéry. Věž byla opravena po částech – v roce 1812 dostala jižní věž novou helmici, druhou věž jen provizorně zakryli. Až roku 1869 obdržel kostel definitivní novogotické helmice.

Poslední vážné poškození pocházelo z konce druhé světové války. Při bombardování Chebu dne 20. dubna 1945 byly věže poškozen. Po válce jím bylo poskytnuto jen provizorní zastřešení sedmi metrů vysokými hlemicemi, které zůstalo nouzovým řešením po dalších šedesát tři let. Teprve v roce 2008, poté co nadační fond Historický Cheb sesbíral potřebné prostředky, byla provedena dlouho odkládaná obnova.

Dnešní chrám vystupuje jako trojlodní gotická halová stavba se čtyřmi klenbními poli vedoucími do raně gotického presbytáře s polygonálním závěrem. Součástí interiéru jsou nástěnné malby z konce patnáctého století, které byly po dlouhém období restaurovány do původní podoby. Vnitřní vybavení pochází z konce devatenáctého století v novogotickém stylu a doplňují jej baroka obrazy a sochy ze osmnáctého století. Návštěva kostela umožní pozorovat skrze jeho stěny více než sedm set let střídajících se stylů a městských osudů.