Podle lidové tradice stávala na tomto místě v centru Stěžer dřevěná kaple a vedle ní ze stejného materiálu též zvonice, prý v byzantinském stylu. V roce 1350 došlo k povýšení kaple na kostel a byl sem dosazen první plebán, přičemž podací právo měl až do svého zničení roku 1421 opatovický klášter. V roce 1352 bylo odtud odváděno 6 grošů papežského desátku. Jeho původní zasvěcení nám není známo. To dnešní kostel získal až roku 1355, kdy si 17. října královéhradecký oltářník neboli rektor oltáře Všech svatých Jan směnil místo s plebánem Kunadem (též zvaným jako Konrád). V roce 1360 si vyměnili místo Petr od sv. Petra v Hradci Králové s plebánem Václavem. O 3 roky později plebán Vilém směnil s Henslinem ze Stěžer čtvrt lánu zádušních polí. Roku 1403 nastoupil po zemřelém plebánu Vilémovi kněz Petr. V roce 1426 se plebán Jan stal oltářníkem v Landeku. Poté zde byli kněží podobojí. Během 15. a 16. století byli jeho patrony Pravětičtí z Pravětic, kteří se jako jediní šlechtici hlásili k vyznání Českých bratří, přijímali podobojí a stěžerský kostel byl otevřeným pro královéhradecké měšťany. Tak tomu bylo až do pobělohorské rekatolizace. Teprve v roce 1700 byl opět stěžerský kostel skutečně katolický. Přestal však být farním a stal se filiálním kostela sv. Anny na Pražském podměstí. Po jeho zbourání byl podřízen kostelu stejného zasvěcení, který byl přenesen do Kuklen. Mše tu byly slouženy minority pouze jednou za 14 dní.
Protože byl postaven plně ze dřeva, časem se na něm objevil zub času, který ho nahlodával stále více. Zchátralý kostel i se sousedící zvonicí byl zbořen roku 1830 (některé prameny uvádějí již rok 1826, kdy měla spadnout jeho klenba), přičemž jeho veškeré zařízení bylo uschováno pro nový svatostánek, jenž nechal svým nákladem vystavět Arnošt hrabě Harrach, který jeho vybudováním pověřil stavitele Jana Havlinu, jenž ho dokončil v roce 1832 (některé zdroje však uvádějí za autora kostela stavitele Jana Kurze, který vybudoval mj. pouchovský kostel sv. Pavla, apoštola). Kostel měl tehdy jen malá okénka ve vrcholu těch dnešních. Roku 1860 zde byla zřízena lokálie a o rok později byla postavena budova pro místního duchovního správce, jímž se stal P. Karel Hojný, kooperátor v Kuklenách. Po bitvě na Chlumu 3. července 1866 vtrhli do obce pruští vojáci, kteří vylomili dveře u sakristie, rozbili monstrance a kalichy, roztrhali matriky a některé dražší věci si odnesli s sebou. 30. června 1870 byl kostel povýšen dekretem biskupské konsistoře na farní (lokálie tu byla již od roku 1861). O 12 let později došlo k jeho opravě a modernizaci, při které došlo k výrazné změně, kdy byla dosavadní malá okénka nahrazena těmi současnými, jež mají připomínat románský sloh. Nová okna byla opatřena rámy z kovaného železa a zasklena silným belgickým sklem, částečně barevným. Zároveň došlo k přeložení dlažby a byl zbudován přístavek pro Boží hrob. Nad vchod do kostela byl umístěn znak hrabat z Harrachů - trojice pštrosích per. V roce 1883 byl kostel přeplněn tak, že se do něho věřící nemohli dostat. Důvodem byly 8denní sv. misie, jichž se zúčastnila řada věřících z celého širého okolí. Roku 1887 byla přistavěna malá věžička na východní části kostela s bání a křížkem. Do ní byl umístěn starý a děravý zvonek z roku 1409. V roce 1890 byla snesena původní plechová střecha a nahrazena břidlicí. Celé zdivo bylo natřeno fermeží a díky tomuto kroku se stal kostel vlhkým a studeným. Z tohoto důvodu byla roku 1907 otlučena stará, fermeží napuštěná omítka. K tomu byl uvnitř pod podlahou vykopán vzduchový kanál s otvory, jež vedly ven, a kostel zůstal znovu nahozen. 1. prosince 1900 byly uvedeny do chodu věžní hodiny. O 17 let později se tu opět uskutečnily velmi navštívené sv. misie. Moderní doba tomuto objektu však mnoho nepřála, takže začal opět chátrat. 24. ledna 1964 byl zapsán do státního seznamu kulturních památek (viz
https://www.pamatkovykatalog.cz/kostel-sv-marka-evangelisty-se-sousosim-sv-jana-nepomuckeho-2149397). Teprve v roce 1979 byla opravena věž a střecha kostela. Tyto práce byly provedeny Jaroslavem Slavíčkem a Ladislavem Křížem, přičemž náklad na ně byl uhrazen sbírkou mezi občany a příspěvkem římskokatolické církve. Netrvalo dlouho a v letech 1981-1982 došlo ke generální opravě fasády, věže, oken, hromosvodů a věžních hodin. Nejvíce se o tuto záslužnou práci zasloužili: truhlář Miloš Prinz, zámečnící Jaroslav Slavíček, František Hajpišl, Jaroslav Frýda a hodiny opravili Zdeněk Hátle a Vlasta Kavalírová. Roku 2003 získal chrám nové noční osvětlení. V roce 2007 byl kostel Oldřichem Miškou znovu vymalován a došlo též k rekonstrukci varhan. V současnosti probíhá jeho vnější obnova. K mnohému by nedošlo, kdyby nebyl vznikl Kruh přátel umění evangelisty sv. Marka, o. s. (viz
https://www.stezery.cz/kruh-pratel-umeni-evangelisty-sv-marka-o-s/ds-1232).
Kostel sestává z jedné lodi o 2 polích s osmibokým sanktusníkem s nízkou malou kopulí, k níž na východní straně přiléhá kněžiště o jednom poli a závěru o 3 stranách osmistěnu a jednopatrové věže s čtyřbokou bání s lucernou nad západním průčelím s jediným vchodem v pravoúhlém kamenném ostění, nad nímž se nachází harrachovský kamenný erb. Okna kostela i věže jsou rozdílná, protože jsou dílem obloukovitá a dílem obloukem uzavřená (loď) nebo pravoúhlá (sakristie). Uvnitř je loď sklenuta ve 2 polích českou klenbou a oddělena od eliptickou bání zaklenutého kněžiště vítězným obloukem. V pozadí lodi je navíc vestavěna na 2 čtyřbokých pilířích kruchta.
Na hlavním oltáři je zavěšen obraz sv. Marka od J. Palmeho, který koupila na výstavě v Mnichově roku 1845 hraběnka Anna z Harrachů, rozená Lobkovicová, manželka Františka Antonína z Harrachů, a to za 500 zl. konv. měny. Vedle oltáře stojí socha sv. Václava a socha sv. Ludmily. Postranní oltáře jsou zasvěceny sv. Janu Nepomuckému a Panně Marii. Proti kazatelně je postaven nádherně řezaný kříž od Josefa Hudce z 18. století. Zajímavostí je též tepaná, stříbrná, věčná lampa a mozaikový Boží hrob. Varhany zhotovil v roce 1833 Johann Franz Gottwald ze Lhoty u Semil. K jejich opravě došlo v letech 1883 (Adolf Hanisch), 1994 (Karel Synek z Hradce Králové) a 2008 (Ivan Červenka). V kněžišti za oltářem jsou zazděny náhrobní desky z let 1586 (syn Albrechta Klusáka z Kostelce), 1592 (Václav Mladota ze Solopisk) a 1612 (Adam Pravětický z Pravětic). Z vnější strany kostela je vsazeno do zdi několik náhrobních desek bývalých stěžerských pánů, které byly přeneseny při ukončení pohřbívání kolem kostela, když byl zřízen hřbitov nový na západním okraji Stěžer. Tyto desky pocházejí z let 1603 (Johanka, manželka Adama Pravětického z Pravětic a na Stěžeřích), 1607 (Hynek Pravětický z Pravětic a na Stěžeřích) a 1616 (neznámá žena, nejspíše z téhož rodu).
Na věži původně visela čtveřice zvonů: první s reliéfy Krista na kříži, sv. Jana Nepomuckého, sv. Marka a sv. Václava byl vysoký 82 cm, v průměru měl 94 cm, vážil 500 kg a nesl nápis: "Zu Gottes Ehre bin ich gegossen, Pangratius Drak hat mich gegossen in Königgrätz 1723."(z roku 1723 od Ignáce Dracka z Hradce Králové, na srdci měl uveden rok 1812, některé prameny uváději jako dobu jeho vzniku až rok 1793); druhý od královéhradeckého zvonaře Antonína Schneidera z roku 1813 (tehdy byl pouze přelit) byl vysoký 60 cm, v průměru měl 77 cm, vážil 252 kg a nesl text: „Gos mich Anton Schneider in Königgrätz 1813.“; třetí z roku 1409 byl vysoký 38 cm, v průměru měl 42 cm, vážil 53 kg a byl opatřen textem: „Anno domini mccccix est fusa.“ (podle dašického faráře P. Josefa Nechvíleho zněl nápis takto: "Anno Domini MC C CCIX fusa sum."); čtvrtý byl Nový zvon, tzv. umíráček. V nepřístupném sanktusníku visel novější zvon a vedle něho zde byl uschován starý děravý zvon, který nebyl používán. Poté však přišla 1. světová válka a období rekvizicí. 29. srpna 1916 byly zrekvírovány 2 zvony, z nichž jeden byl z roku 1723. V dubnu 1918 byly odebrány další 2 zvony, z nichž jeden byl z roku 1813. Ve věži zůstal pouze zvon z roku 1409, neboť úřední nařízení nedovolovalo ničit historicky cenné zvony. V roce 1922 byl koupen od V. Červeného z Hradce Králové 150 kg těžký zvon a roku 1928 430 kg vážící zvon s nápisem: ,,Nedej zahynouti nám ni budoucím“ od firmy Buřil a Riss v Kuklenách. Oba byly pořízeny ze záduší, a to za 9 150 a 12 000 Kč. Netrvalo však dlouho a oba měly stejný osud jako jejich předchůdci. 27. března 1942 byly zrekvírovány německými okupanty. Zůstal opět jen zvon z roku 1409 (dílo „Královéhradecko“ od L. Domečky a F. L. Sála hovoří o tom, že pochází z roku 1460). Ten byl po roce 1989 zrestaurován Pavlem Kováčem. 25. září 2016 byl posvěcen nový zvon sv. Václav od Michala Votruby z Myslkovic, který má průměr 79,5 cm a hmotnost 342,5 kg. Jako zajímavost uveďme, že reliéfní výzdoba byla sňata ze sádrové repliky zvonu z roku 1723. 30. dubna 2017 byl posvěcen zvon druhý, který je zasvěcen sv. Ludmile a je ozdoben obecním znakem.
Navíc před vchodem do kostela, jenž je dnes filiálním k pražskopředměstské farnosti, stojí na místě bývalého hřbitova socha sv. Jana Nepomuckého s harrachovským znakem z roku 1863 s nápisem: „DIVo IoannI In Vers orbIs ChrIstIannI InsIgnI thaVMat Vrgo Ita erIgI CvraVIt Vera et Integra pIetas stIeserIensIs“ (1755). Na jižní straně kostela se nachází velký železný kříž z harrachovských sléváren, který původně stál na místě, kde se křižují silnice k Hřibsku a Těchlovicím (posvěcen 25. dubna 1881, v roce 1908 se na jeho místě měla stavět hasičská kolna, proto byl přenesen ke kostelu) a na té východní socha Panny Marie s Jezulátkem z roku 1873.