Kostel byl postaven v renesančním stylu knížetem Karlem z Münsterberka v letech 1606 - 1610. Jeho nynější podoba pochází ze čtyřicátých let 19. st. a nese znaky tehdy módního pozdního empíru. Oltář vytvořil v první polovině 19. st. slezský sochař Cyril Kutzer. Na hlavním oltáři je umístěna Madona od Jiřího Antonína Heinze, v presbytáři je zavěšen renesanční krucifix a dvě barokní plátna, z nichž menší namaloval Johan Christoph Handke. Výtvarně hodnotné jsou i lavice, z větší části pořízené v roce 1778 spolu s intarzovanými vstupními dveřmi. Na kostelní věži je zavěšen zvon, který odlil Hans Pauer v roce 1584. Mezi opěráky závěru presbytáře byla v roce 1750 vystavěna grotta a v ní umístěno dílo neznámého umělce, takzvaného "moravsko-třebovského okruhu", sousoší Kristus na hoře Olivetské. Současná podoba grotty je dílem Lubomíra Dostála, sochy restaurovala Romana Balcarová.

Kostel Povýšení svatého Kříže (dříve svatého Linharta) stojí na místě nejstarší křesťanské svatyně, jejíž původ sahá k samým počátkům města. Nynější stavba byla dokončena v roce 1754 podle plánů fulneckého stavitele Mikuláše Thalherra. Zařízení interiéru z druhé poloviny 18. a 19. století bylo zcela zničeno po roce 1945. V letech 1998 a 1999 byl z prostředků Ministerstva vnitra Spolkové republiky Německo obnoven podle původních plánů exteriér kostela. Kostel slouží, kromě bohoslužeb na svátek Povýšení svatého Kříže, k výstavám a koncertům.