Kostel Nanebevzetí Panny Marie v Letohradě-Orlici pochází z počátku 18. století a nalézá se na místě, kde před ním stávaly již dva starší kostely. Od roku 1964 je chráněn jako kulturní památka České republiky.
První kostel stával v Orlici s jistotou již ve 14. století, jak dokládají první písemné zmínky. Zřejmě za husitských válek byl však zničen. Po roce 1450 zde byl vystavěn další kostel, navštěvovaný obyvateli převládajícího českobratrského vyznání. Zvony z tohoto kostela, pocházející z roku 1497 a 1498, se zachovaly dodnes.
Po roce 1620 zůstal orlický kostel brzy prázdný. Fara byl později přemístěna do Lukavice, jedním z důvodů tohoto kroku mohla být silná českobratrská tradice, která byla ke kostelu vázána.
Dne 5. června 1709 byl na místě staršího kostela položen základní kámen kostela nového. Stavbu řídil kyšperský stavitel Andreas Casteli. V kostele byly tři oltáře, hlavní s obrazem Nanebevzetí P. Marie, boční pak zasvěcené sv. Barboře a sv. Františku de Paula. V roce 1759 sem byla umístěna křížová cesta v bohatě zdobených rokokových rámech. Autorem maleb byl dvorní malíř císařovny Marie Terezie Johann Bergla za dílo obdržel honorář 2 000 zlatých. Jednotlivá plátna mají rozměry 140 x 210. Jejich zavěšení a posvěcení se uskutečnilo dne 2. července 1759.
V roce 2009 prošel interiér kostela rekonstrukcí, během níž byl nově vymalován, osvětlen a ozvučen. Zásadních změn doznalo uspořádání jeho interiéru, jehož orientace byla změněna. Nový kamenný obětní stůl byl netradičně umístěn na střed boční stěny lodě. Byly odstraněny původní boční oltáře a kazatelna a sňaty obrazy křížové cesty. U dřevěných objektů bylo zjištěno jejich napadení červotočem a obrazy křížové cesty byly určeny k restaurování.
