Zalaegerszeg első plébániatemplomát Mária Magdolna tiszteletére építették a XIII. század első felében, s ennek helyére-köré emelték a jelenleg is meglévő templomot, melynek alapkövét 1747-ben tették le. Ám tíz évvel később még mindig csak a szentély került tető alá. A munkálatokat tragikus esemény gyorsította fel: 1760. május 18-án tűzvész pusztított a városban, közel kétszáz ember maradt hajlék nélkül. A régi templom végső romlása is ekkor következett be: az új templom végül 1769-re készült el.
Gyászos esztendő volt 1826 is, amikor egy borzalmas városi tűzvész Isten házát sem kímélte: tetejét és tornyának sisakját elhamvasztotta, harangjai megolvadtak, boltozatát megrongálta.