Kyrkan är uppkallade efter kung Matthias, eller Matthias “den rättvise”, en kung som levde mellan 1443 och 1490. Han gift sig två gånger i denna kyrkan och det är också därför den är uppkallade efter honom. Officiellt så heter den “Vår frus kyrka”. När Turkarna invaderade Ungern/landet tog dem över slottsområdet. Kyrkan blev ett muslimskt bönehus, men användes som stall för sina hästar också. 1686 lyckades man övervinna dem Turkiska styrkorna och staden kom i kristna händer igen. Under slaget, sägs det att en skulptur av Jungfru Maria blev gömd, och plötsligt uppenbarade sig för muslimerna, och deras moral föll och staden föll på samma dag.
På insidan av kyrkan finns det delar som är daterade ända till 1400-talet, orginalstilen hålls dock vid som är gotisk byggnadsstil. Men lägg märke till taket som är gjort i Nouveau stil, väldigt typisk för byggnader ifrån slutet av 1800-talet och början på 1900-talet (när dem renoverade stora delar av kyrkan).