Současná podoba kostela je výsledkem několika stavebních etap. Nejstarší z nich ještě souvisí se Štaufy a hutí, která pracovala na zdejší falci-hradě. Mimo jiné má mnoho společného s katedrálou v Bamberku.

Z původní románské baziliky se zachovaly v Chebu obě věže, západní průčelí s portálem a portál v severní lodi, zbytek stavby je gotický.

K raně gotickému, poměrně úzkému presbytáři s polygonálním závěrem byla časem dostavěna pozdně gotická trojlodní hala, která byla několikrát vyzdobena a nově zařízena – naposledy v novogotickém slohu.