De voorm. Mariakerk (Nieuwe Markt 35) is het overblijfsel van een tegen de noordwesthoek van de St.-Lebuïnuskerk gebouwde laat-gotische driebeukige hallenkerk. De tussen 1235 en 1251 als parochiekerk gestichte kerk werd door de stadsbrand van 1334 verwoest.
Herbouw geschiedde waarschijnlijk in de vorm van een basilicale kerk met rechtgesloten koor, waarvan volgens archeologische opgravingen uit 1961 de zuidbeuk aansloot tegen de noordwestelijke traptoren van het romaanse westwerk van de St.-Lebuïnuskerk. Tussen 1400 en 1458 werd het middenschip vernieuwd en hoewel de pijlers van kolonnetten voorzien zijn, is het onwaarschijnlijk dat een overwelving in steen uitgevoerd werd.
Vermoedelijk werd de noordzijbeuk aan het eind van de 15de eeuw verbreed en verhoogd als eerste fase van de verbouwing tot hallenkerk. Aan de westzijde verrees in 1484 een sacramentskapel.
Nadat men aan het begin van de 16de eeuw definitief had afgezien van de bouw van een tweede westtoren aan de St.-Lebuïnuskerk, kon in 1519-'20 een bredere zuidbeuk gebouwd worden, met gewelven, steunberen en een tufstenen buitenbekleding. In de kap zijn nog de aanzetten van de tweede westtoren te zien.
Uitwendig kreeg de kerk het karakter van een hallenkerk. Doordat men echter de scheibogen in het middenschip niet verhoogde, werd het beoogde effect inwendig niet bereikt.
In 1543 volgde vernieuwing en verhoging van de sacramentskapel. In 1566 hield men hier de eerste protestantse preken en in 1591 onttrok men de kerk wegens overtolligheid aan de eredienst.
Men overwoog volledige sloop, maar uiteindelijk werd in 1612 slechts de noordelijke zijbeuk verkocht voor de bouw van een rij woningen aan de Nieuwe Markt.
Het middenschip werd van kap en houten gewelf ontdaan.
In 1647-'57 werd de zuidelijke zijbeuk in tot arsenaal ingericht. In 1836 nam het Rijk dit deel over en in 1893 verrees een loods in het middenschip.
In 1955 is dit deel aan de gemeente overgedragen en het huisvest na restauratie in 1985 naar plannen van H. Roebbers culturele activiteiten.
Het hoekhuis Nieuwe Markt 33-34 met pothuis werd in de 17de eeuw in de voormalige sacramentskapel gebouwd. Het gepleisterde pand Grote Kerkhof 37 kwam werd in de 18de eeuw aan de westzijde tegen de kerk te staan.
De kameren Grote Kerkhof 38-40 stammen eveneens uit de 18de eeuw en huisvestten oorspronkelijk bejaarde weduwen.
