V roku 1784 sa začala veľká finančná zbierka na stavbu chrámu na pozemku pri stoličnom dome. Základný kameň položili 19. marca 1784. Kostol stavali z kameňa s drevenou povalou bez veže. Práce dokončili v tom 24. júna toho istého roku. V roku 1842 realizovali ďalšie práce na kostole a stavbu veže so zvonmi. O rok neskôr dali veriaci v Pešti zhotoviť nový pol tony vážiaci zvon. Dochoval sa až do dnešných čias, aj keď na konci 20. storočia praskol a nanovo ho vyhotovili z toho istého materiálu.
V roku 1893 časť mesta zasiahol veľký požiar. Zhorel aj tolerančný kostol. Cirkev sa rozhodla postaviť nový a väčší na tom istom mieste. Farár Pavol Samuel Novák organizoval domáce a najmä zahraničné zbierky na výstavbu, ktorá prebiehala v rokoch 1893 – 1894 na základe projektov Félixa Bullu. Oltár, kazateľňa a krstiteľnica je dielom rezbárskej školy v Bardejove. Chrám vysvätili 25. novembra 1894. Po smrti Pavla Samuela Nováka v roku 1925 tam pôsobil farár Ján Bezek z Liptovského Petra až do konca 2. svetovej vojny. V roku 1934 vymaľovali interiér podľa návrhu akademického maliara Jána Hálu. Autorom maľby je Anton Bodnár. Uskutočnili tiež generálnu opravu fasády a rekonštrukciu elektroinštalácie.
Kostol opäť rekonštruovali na prelome sedemdesiatych a osemdesiatych rokov 20. storočia. Dôvodom bola vysoká vlhkosť muriva. V predsieni kostola je umiestnená tabuľa padlých počas rokov 1914 – 1918. Na budove fary oproti kostolu sa nachádza pamätná tabuľa Samuela Nováka.
