Původně gotický kostel sv. Máří Magdalény v Kamenné Horce byl postaven asi v první polovině 14. století. V roce 1749 byl s přispěním obce a finančních darů zcela přestavěn do nynější barokní podoby. Jedná se o jednolodní obdélníkovou stavbu s čtvercovým presbytářem se sakristií a oratoří. Hlavní loď je zaklenuta valenou klenbou s lunetami. V roce 1804 byl kostel slavnostně vysvěcen. Hlavní raně barokní oltář byl osazen koncem 17. století a ve 2. polovině 19. století upraven a doplněn sochami.
Vstup do kostela představuje původní pozdně gotická hranolová zvonice. Pochází snad z 2. poloviny 15. století a sloužila jako část opevnění samotného kostela. Čtvercový půdorys věže s masivními, téměř dva metry silnými stěnami rovněž ukazuje na obranný charakter věže, stejně jako horní dřevěné patro s otevřenými střílnami v podsebití. Věž sloužila nejen jako zvonice, ale i jako útočiště před nepřítelem, jak o tom vypráví pověst z třicetileté války.
V r. 2011 byla dokončena I. etapa opravy kostela – vnější část.
Pouť se zde slaví v červenci.