Ten gevolge van een conflict met Steven van Lienden brandt in 1400 nagenoeg de hele stad af. Ook de Cunerakerk en het Raadhuis met alle archieven gaan in vlammen op. Dat ook de oorspronkelijke stadsbrief verloren gaat, blijkt uit het feit dat de Utrechtse bisschop Frederik van Blankenheim in 1403 de stadsrechten herbevestigt.
Waarschijnlijk was de voorganger van de huidige kerk in Romaanse stijl gebouwd, maar daar is nog nooit oudheidkundig bodemonderzoek naar gedaan.
De herbouw begint bij het koor. De toenemende bijdragen van de pelgrims maken het mogelijk om steeds rijker te bouwen. Vooral aan de buitenzijde (bij de steunberen) valt het op dat de versiering van oost naar west steeds rijker wordt. Algemeen wordt aangenomen dat de herbouw plaatsvindt tussen 1400 en 1475.
Al in 1492 beschikken de kerkmeesters over voldoende middelen om met de bouw van de toren te beginnen. In 1531 is de 80 meter hoge ‘Cunera’ voltooid; geen geringe prestatie voor een stadje met hooguit 700 inwoners.
Over bouwmeesters wordt in de rekeningen slechts zijdelings iets vermeld:     
ene ‘meister Clement’  wordt in 1519 getrakteerd op enkele kannen wijn en hij ontvangt een fors jaargeld. Men neemt aan dat er een wijziging in het ontwerp plaatsvindt na de bouw van het eerste vierkant. In het onderste deel worden 5 rijen baksteen afgewisseld door een laag natuursteen; de zgn. speklagen. Hogerop treft men in het zicht vrijwel uitsluitend natuursteen aan. 
Rond 1550/60 schaft men het oksaal aan en in 1570 volgen de koorbanken met de sedilia priestergestoelte). Bij de reformatie (in Rhenen in 1578) gaat de kerk over in protestantse handen. Waarschijnlijk wordt er weinig vernield, maar de meeste heiligenbeelden en alle altaren worden verwijderd. Buiten diverse restauraties is er nadien nauwelijks iets gewijzigd.