Zdejší kostel byl již ve 14. století farním, přičemž byl opatřený zvláštním plebánem, který patřil pod dobrušského děkana a královéhradeckého arciděkana. Poprvé byl zmíněn roku 1355 pod patronátem Alberta z Rýzmburka. V letech 1384-1405 odváděl 3 groše papežského desátku. Roku 1355 třebešovský plebán uváděl plebána v Náchodě. V roce 1361 byl zdejší kněz Jan dosazen za plebána do Orlice. 20. července 1386 dosadil probošt jaroměřského kláštera Jakub klášterníka Mikuláše za plebána do Třebešova. Roku 1391 si třebešovský plebán Jan směnil místo s Benešem, oltářníkem u sv. Kateřiny v Častolovicích, a to s povolením probošta jaroměřského kláštera Jakuba, převora Henlina a ostatních řeholních bratří. O 6 let později zemřel třebešovský plebán Petr a na jeho místo dosadil jaroměřský klášter klášterníka Jana Pecolda, rodáka ze Dvora Králové nad Labem. 29. září 1409 odkázal Pešík řečený Chřipta ze Zblova půl kopy grošů ročního úroku na svém zboží Miskolezech ke kostelu v Třebešově za duši své manželky Zdeny. Během husitských válek ztratil kostel svého plebána a později byl jako filiální připojen ke kostelu v Malé Skalici (dnes Česká Skalice). Roku 1436 získal podací právo Jiří z Chvalkovic a po něm jeho dědicové. V roce 1603 koupil oba Třebešovy a půl Litoboře Albrecht Václav Smiřický ze Smiřic na Náchodě, který je spojil s náchodským panstvím. První oprava kostela byla provedena v roce 1678, čehož důkazem je nápis umístěný pod chorem: „Ao 1678 14. Novbr. tento chram Panie gest okrasslen za důst. p. Girziho Antonina Hanuchy protonotariusa aposstolskeho fararze Skaliczkeho.“ Větších oprav se objekt dočkal roku 1858, kdy byl dáván rákosový strop, nová dlažba, kostel byl vybílen, pořízeny obrazy sv. Štěpána na velký a sv. Václava a Vojtěcha na postranní oltáře. V roce 1904 došlo k obnově celého interiéru kostela. 23. června 1906 navštívil kostel královéhradecký biskup Msgre. ThDr. Josef Doubrava. 10. března 1964 byl objekt zapsán do státního seznamu kulturních památek (viz
https://pamatkovykatalog.cz/kostel-sv-stepana-12816037). Roku 2004 byla provedena oprava poloviny kostela, který získal též novou fasádu. Později došlo i na další práce, jež probíhají postupně i v současné době, např. v letech 2023-2024 šlo o ohradní zeď.
Jedná se o jednolodní orientovanou stavbu s původní sakristií na severu, se zbarokizovanou lodí a hranolovitou věží, přilehlou na severu k lodi. Nejstarší částí této stavby se sedlovou střechou je gotické presbyterium, sklenuté do kamene, z čehož děkan Rojek soudil, že pochází z roku 1300. Tvoří nepravidelný pětistěn, 2 okna klenuté do ostrého bodu, ale bez kružeb, třetí je podlouhlé. Žebra klenutí se sbíhají nahoře v růži, dole pak nesou 4 konzolky, 3 lidské tváře hrubě dělané, čtvrtá pak neznalá. Kápěmi křížové klenby sklenuté kněžiště je pak opřeno trojicí opěráků. Triumfální oblouk je hrotitý s náběžní římsou. Západní průčelí s lizénovými rámy je trojosé, zakončené profilovanou římsou a štítem s konkávně vykrojenými křídly a trojúhelným tympanonem. Hrotitou valenou klenbou zaklenutá sakristie má na rozdíl od lodi pultovou střechu, podvěží má naopak valenou klenbu.
Zařízení je raně barokní a pochází z 2. poloviny 17. století, přičemž o 2 století později došlo k řadě jeho úprav. Hlavní oltář sv. Štěpána má obraz malovaný na plátně z roku 1858, který představuje klečícího a hledícího do nebe sv. jáhna a nad ním vznášející anděly s palmou vítězství. Po stranách stojí dvojice dřevěných soch, jedna s kalichem (snad evangelista sv. Jan) a druhá představuje sv. Josefa s malým Ježíšem Kristem. Nad hlavním obrazem je nápis: „Fulcite me floribus, stipate me malis“. Presbyterium je od lodi odděleno do ostrého bodu sklenutým vítězným obloukem, na jehož straně do lodi je v zeleném věnci uveden dvojí letopočet opravy (1687 a 1858). Loď je copová s obyčejnými segmentovými okny, plochý strop je pak zhotovený na rákos, který byl dříve prkenný a ozdobený různými motivy. Malovaný dřevěný strop s ornamenty vymalovanými v lidové tradici můžeme stále nalézt pod kruchtou. Postranní oltáře jsou 2, a to sv. Václava a sv. Vojtěcha. Prkenné zábradlí choru nese 10 maleb ze života Ježíše Krista a Panny Marie. Za zmínku stojí též stará, ničím nezdobená kropenka s vnitřní mramorovou mísou. Sakristie po straně evangelia a předsíňka do kostela jsou copové. Kamenná křtitelnice pochází z 15. století. Varhany mají pocházet ze 2. poloviny 18. století a podle všeho je zhotovil Adalbert Schreyer. V roce 1927 byly opraveny Václavem Poláčkem z Rychnova nad Kněžnou a roku 1965 Františkem Čálkem (viz
http://www.varhany.net/cardheader.php?lok=3973). Uvnitř lodi blíže předsíňky je ve zdi 9 náhrobníků bývalých vlastníků Třebešova a Miskolez, většinou Dobřenských z Dobřenic, jež bývaly původně venku za kostelem, ale díky c. k. okresnímu školnímu inspektorovi J. K. Hrašemu byly zasazeny do zdi uvnitř kostela.
V průčelí kostela je kamenná, čtverhranná zvonice končící bání s lucernou a hrotnicí, v níž původně visela pětice zvonů. První o výšce 0,93 m, průměru 1,05 m a s nápisem: „WALENTIN LISSIACK HAT MICH GEGOSSEN IN DER KÖNIGL. KLEIN RESIDENZ STADT PRAG 1746. GA ZWON WACLAW IAN W PRAZE VDIELAN A KRZTIEN GSEM ZA PANA WYS. OSW. KNIŽETE P. T. OCTAWIA PICCOLOMINI Z ARAGONU. GENERAL FELDT MARSCHALL LIEUTNANT. TITL. P. WACZL. WOGT. IANA KLUGAR FARARZE. P. ANTON IOSEPH FRITZ. HEGTMANA MARTINA SEDLACZKA KANTORA IAKOBA PITASSE KOSTELNIKA NAKLADEM ZADUSS PRZELITY.“; druhý o výšce 0,78 m, průměru 0,80 m a s textem: „tento zwon slit gest M. V. C. (1500). ke czti a chwale božie a swatemu sstiepanu do trzebessowa.“; třetí o výšce 0,63 m, průměru 0,66 m a s nápisem: „tento zwon teto obczy pane boze racz zdarzyty“, který musel vzniknout před rokem 1480; čtvrtý o výšce a průměru 0,35 m a s reliéfem Jana Nepomuckého z 2. poloviny 18. století a pátý o výšce 0,15 m z 1. poloviny 19. století.