De eerste Parochiekerk van Harderwijk was de Sint Nicolaaskerk, die even buiten de muren van de stad lag. In 1415, toen de toren van genoemde kerk door brand werd beschadigd, werd toestemming verkregen om binnen de muren een nieuwe parochiekerk te bouwen. In de stad had men al de Onze Lieve vrouwe Kapel (14e eeuw). Deze kapel, in afmeting ongeveer 30 bij 21 meter, werd uitgebreid naar de thans bekende afmetingen en kon als nieuwe parochiekerk in gebruik genomen worden. Tegelijkertijd begon men met de bouw van de toren die ongeveer in 1440 voltooid was.
In 1503 vond in Harderwijk een zeer grote stadsbrand plaats, waarbij ook de kerk zwaar beschadigd werd. Met name de bekapping ging verloren. Het herstel duurde tot ongeveer 1560. In de jaren daarna werden de gewelven beschilderd door Ewold van Delft. Enige jaren daarna, in 1578, vond de reformatie ook in Harderwijk plaats. De schilderingen werden wit gekalkt en er verdwenen veel beelden en altaren uit de kerk. Wel kwam er in 1614 een nieuwe en fraaie preekstoel.
Dieptepunt in de historie van de kerk was de ineenstorting van de toren, waarbij ook het halve schip werd vernietigd. Tegen het overgebleven deel van het Schip werd een nieuwe westgevel geplaatst.
Vanaf 1967 werd de kerk uitgebreid gerestaureerd. Veel tijd en energie werd gestoken in het tevoorschijn halen (van onder vele lagen kalk) van de gewelfschilderingen uit 1562. Deze vormen een van de voornaamste bezienswaardigheden van de kerk. Ook de fraaie gewelven zijn het aanzien meer dan waard. Tijdens de restauratie werd ook de vieringtoren, die 200 jaar eerder was afgebroken, hersteld. De toren werd voorzien van een carillon dat later nog eens werd uitgebreid tot 47 klokken.