Soupis o farnosti v Hoštějně sahá až do roku 1351, kdy je připomínána v listině o založení biskupství litomyšlského. Středověký kostel však zanikl v průběhu patnáctého století spolu s hradem. Naposledy je doložen v pramenech roku 1480 v souvislosti s náhrobkem Smila ze Šternberka, někdejšího majitele hoštejnského panství. Od druhé poloviny sedmnáctého století závěsela Hoštejn farnosti v sousedním Zábřehu, později pak v Dolní Hynčině.

Teprve koncem osmnáctého století se v místě zrodila naděje na nové sakrální centrum. Postavena byla kaple svaté Anny, u níž byl posteriormente zřízen i nový hřbitov. O padesát let později, v roce 1815, přeměnili kapli v malý kostelík vybavený sakristií. Nový kostel měl varhany, oltář, kazatelnu a křtitelnici, k vybavení patřily rovněž dva zvony a devět lavic. Rostoucí obec se však s časem potýkala s nevyhovujícím stavem stavby. V roce 1865 proto vypracovali stavbytelé plány na podstatnou přestavbu a rozšíření. Stavební práce proběhly v druhé polovině šedesátých let a kostel byl slavnostně vysvěcen v roce 1869 jako moderní romantická stavba.

V následujících desetiletích se Hoštejn stal vyhledávaným místem každoroční poutě, která se konala v neděli po svátku svaté Anny. Roku 1903 byly pořízeny nové varhany, o rok dříve, v roce 1892, byla obnovena i nedaleká fara. Třicátá léta dvacátého století přinesla nezbytné opravy, výraznější obnova pak nastala v osmdesátých letech pod vedením faráře Josefa Hrdličky, pozdějšího olomouckého světícího biskupa.

Architektonicky je kostel výrazným příspěvkem romantismu. Postaven na příkrém návrší, jeho dvoubarevná fasáda učinila jej zdaleka viditelnou dominantou. Stavba má jednolodní obdélný půdorys s polygonálně zakončeným odsazeným presbytářem. Charakter prostoru určuje kvadratická věž s vysokým štíhlým jehlanem a makovicí, zdvihající se z hřebenu střechy nad vchodem. Vysoká okna se zaoblenými záklenky jsou zdobena vitrážemi. U presbytáře je přistavěna nízká sakristie. Vchod do chrámu tvoří dvoukřídlé dřevěné dveře s obloukovým zakončením, chráněné shora ozdobným štítem na dvou štíhlých sloupcích. Před západní zdí u vchodu stojí ochranný litinový kříž na podstavci z pískovce s polychromovanými reliéfy Panny Marie, svaté Barbory a archanděla Michaela.

Mezi cenné součásti vybavení patří mešní kalich z roku 1629, zdobený prolamovaným vegetativním ornamentem, a zvon z roku 1769, původně zhotovený pro obec Javoří. Interiér dominuje novogotickým hlavním oltářem s obrazem svaté Anny. Od roku 2001 se kostel dočkal celkové rekonstrukce trvající osm let, během níž byl restaurován oltář, dřevěné zábradlí chórového kůru a opraveny varhany. V roce 2003 instaloval akademický sochař Petr Váňa nový oltářní stůl, ambon a sedes. Okna byla postupně zdobena vitrážemi znázorňujícími křesťanské svátosti a na čelní stěně se objevila vitráž s postavou patronky chrámu.

Dnes zůstává kostel živou součástí obce a populárním poutním místem. Vedle věřících jej navštěvují i milovníci architektury a historie. Zajímavostí je, že v půdních prostorách kostela se usídlila kolonie chráněných netopýrů velkých, kterým zde poskytuje bezpečí a útulnou domácnost.