Hřbitovní kostel Nalezení sv. Kříže postavený na kopci nad Moravskou Třebovou fungoval už v závěru 15. století. V roce 1602 městská rada rozhodla o demolici středověké budovy a jejím nahrazení novostavbou. Stavitel Andreas Balzer ze slezské Nysy zde na obdélném půdorysu realizoval halový prostor. Širší hlavní loď je od užších vedlejších oddělena hrotitými oblouky sklenutými na masivní sloupy s polygonálním půdorysem. Na loď navazuje polygonálně uzavřený presbytář. Kostelní novostavba vznikala mezi lety 1603–1605 a o rok později se vybavovala mobiliářem. Klenba musela být i s dekorem hotová nejpozději v roce 1605. Kromě Andrease Balzera je zde jménem doložen také sochařský mistr Christoph, kterému se platilo za kamenické prvky (sloupy, ostění atp.). Interiér kostela byl náročně vybaven, ale jeho renesanční podoba byla několikrát upravena. Poprvé zřejmě v souvislosti s rekatolizací a novým vysvěcením v roce 1631, kdy byly odstraněny náhrobky a epitafy, dále v barokním období a na přelomu 19. a 20. století, kdy byla realizována současná výmalba lodi. 

Interiér kostela je sklenut valenými klenbami s trojbokými výsečemi. Původní štuková dekorace se zachovala jen ve fragmentech v podobě konzol a dekorativních žeber. Konzoly byly dříve označovány jako pískovcové (Říhová 2011, s. 127), jsou však provedeny z vytlačovaného štuku a v jednom případě se dekorace opakuje, tedy byla vytlačena ze stejné formy. Výběhy na severní a jižní stěně jsou opatřeny dekorem okřídlené andílčí hlavičky, vegetabilního závěsu, či části pásového ornamentálního dekoru s hlavičkou ve středu. V koutech se zachovaly kuželové konzoly opatřené kanelurou a zubořezem. Při restaurování renesančních maleb interiéru byla odhalena také původní okrová barevnost některých konzol. Okrová byla i žebra, která tvořila základ dekorativního klenebního vzorce. V koutě lodi u vítězného oblouku se v prostoru za bočním oltářem zachovala destruovaná žebra tvořená masivním pletencem rámovaným kulatými perlami perlovce. O rozmístění dekorativních žeber si můžeme z části udělat představu díky negativním otiskům v ploše klenby patrným při ostrém bočním osvětlení. V  hlavní lodi bylo centrální kosočtverečné zrcadlo vytvořené křížením žeber stýkajících se v kruhových svornících. Další plochy členila atektonicky umístěná křížící se žebra.