Prvý kostol bol postavený v 11. storočí na námestí mesta. Obyvateľstvo tu bolo katolícke. Pôvodný gotický kostol pochádzal pravdepodobne zo 14. storočia. Počas archeologického výskumu námestia v rokoch 1994 až 1997 sa našli základy staršej gotickej stavby. Ján Jiskra z Brandýsa v 15. storočí opevnil kostol hradbami. Po reformácii Luthera a Kalvína sa udiali zmeny aj v Rimavskej Sobote.
V roku 1524 sa vysokopostavený predstaviteľ cirkvi, katolícky kňaz Em. Bebek oženil a nariadil prijať učenie Luthera. V roku 1594 tu boli nasledovatelia Jána Kalvína vo väčšine. V čase reformácie v rokoch 1592 až 1769 patril kostol takmer 177 rokov kalvínom. Veriaci chodili na sväté omše do kaplnky Panny Márie, ktorá stála pri kostole a pochádzala z polovice 16. storočia alebo sa modlili na cintoríne. Náklady na výstavbu kaplnky hradil šľachetný mešťan János Warga.
Kostol, ktorý stál na námestí, bol pôvodne katolícky, ale po reformácii ho používali kalvíni. V roku 1769 prebiehali boje medzi katolíkmi a kalvínmi o prinavrátenie kostola. Zmena nastála až počas vlády Márie Terézie. Kráľovský súd 9. apríla 1771 rozhodol v prospech katolíkov. Po skončení súdu sa György Karaba stal prvým katolíckym farárom. Pôvodný kostol bol už starý a poškodený, hrozilo jeho zrútenie. Preto Mária Terézia v roku 1774 alebo 1775 dala zbúrať a postaviť nový kostol, ktorý stojí dodnes. O tom svedčí aj latinský nadpis nad jeho vchodom:
Hex augusta – Vznešená kráľovná
Maria Theresia – Mária Terézia
Deo et Catholicis posuit – Dala postaviť Bohu a katolíkom
