První písemná zmínka o Slezských Rudolticích je z roku1255roku 1255. O původním dřevěném kostelu jsou první písemné zmínky v roce 1671. Kostel měl i dva zvony, jeden z roku 1557. V roce 1870 vypracoval plán nového kostela arcibiskupský architekt [[Gustav Meretta]]. Výstavba novorománského kostela byla zahájená demolicí sterého kostela v roce 1871 a na téměř stejném místě a téhož roku byl postaven firmou krnovského stavitele [[Ernst Latzel|Ernsta Latzela]] kostel nový. Stavba byla dokončena v roce 1874, ale dokončovací sochařské práce pokračovaly až do roku 1875.<ref>{{Citace elektronického periodika|příjmení=|jméno=|titul=Kostel sv. Kateřiny|periodikum=www.slezskerudoltice.cz|vydavatel=|url=http://www.slezskerudoltice.cz/informace-o-obci/kostel-sv-kateriny/|datum vydání=|jazyk=cs|datum přístupu=2017-03-15}}</ref> Z krypty starého kostela byly vyzvednuty ostatky rodu Hodiců s náhrobky a přeneseny do krypty v lodi nového kostela, který byl [[Svěcení|vysvěcen]] 29. června 1875.<ref>{{Citace elektronického periodika|příjmení=|jméno=|titul=Kostel svaté Kateřiny|periodikum=www.osoblazsko.cz|vydavatel=|url=http://www.osoblazsko.cz/encyklopedie/objekty1.phtml?id=101679&id_obce_3=72515|datum vydání=|datum přístupu=2017-03-16}}</ref> V roce 1932 byl kostel elektrifikován.
Hřbitov kolem kostela byl zrušen v roce 1804.<ref>{{Citace elektronického periodika|titul=Zajímavosti :: Mikroregion Osoblažsko|periodikum=www.mikroregion-osoblazsko.cz|url=http://www.mikroregion-osoblazsko.cz/clenove/slezske-rudoltice/zajimavosti/|jazyk=cs|datum přístupu=2017-03-15}}</ref>
