Rímskokatolícky kostol sv. Štefana prvomučeníka je najstaršia stavba vo Východnej. Podľa doterajších poznatkov ho postavili v 15. storočí. Keďže o tomto období Východnej nemáme zatiaľ žiadne informácie, môžeme iba predpokladať, že o výstavbu kostola sa pričinili farári z Hýb, ktorí v hybskom rímskokatolíckom kostole Všetkých svätých slúžili už od začiatku 14. storočia a okrem krátkeho obdobia (1687-1698) vykonávali cirkevné obrady až do roku 1943 aj vo Východnej.
Pôvodne to bola neveľká, jednoduchá jednoloďová stavba s polygonálnym presbytériom a bez veže. Počas piatich storočí nadobúdal kostol nové podoby. Najstaršie známe stavebné zmeny sú zaznamenané na jeho vstupnom portáli z tesaného pieskovca s čoraz ťažšie čitateľným nápisom Andraz Schuri 1618 z Wichodnej. Dá sa z neho usúdiť, že vtedy pristavili ku kostolu nízku vežu, na ktorú v rokoch 1634 a 1636 zavesili prvé zvony. Z tohto obdobia akiste pochádzajú aj vstupné gotické, plechom obité dvere a stará kamenná svätenička, ktorá donedávna ležala medzi náhrobnými kameňmi niekdajšieho prikostolného cintorína.
Ďalšie, žiaľ podrobnejšie nešpecifikované úpravy sa spomínajú z rokov 1727 a 1803. V roku 1827 nadstavili vežu do súčasnej výšky. Vystupovalo sa ňu drevenými schodmi s prístreším na jej južnej strane. V roku 1834 zavesili na nadstavenú vežu terajší veľký zvon, ktorý preliali zo zvona uliateho na počesť sv. Štefana z roku 1634. V tomto období svätyňu zaklenuli plochou pruskou klenbou a vo vstupnej predsieni („babienci“) urobili krížovú klenbu. Vtedy pravdepodobne pristavali aj sakristiu, čím kostol nadobudol súčasné pôdorysné rozmery 12 x 21 metrov.
Ďalšie stavebné práce sa datujú do roku 1928. Spočívali vo zväčšení troch „románskych“ okrúhlych okien v chrámovej lodi za účelom zlepšiť osvetlenie kostola. Dovtedy mali tvar a veľkosť ako terajšie okienka nad chórom. Pri tejto príležitosti vymenili drevené rámy na všetkých oknách za železné, ktoré zhotovil miestny zámočník Ondrej Števček. Murárske práce a vybielenie kostola zverili murárskym majstrom Michalovi a Jozefovi Majerčíkovcom. Súčasťou úprav bolo zavedenie elektrického osvetlenia kostola, inštalácia bleskozvodu a výmena „šalogatrov“ na kostolnej veži za terajšie kovové.
Strecha kostola bola pôvodne pokrytá šindľom. Jeho výmenu spomínajú staré spisy z rokov 1924 a 1949. V šesťdesiatych rokoch minulého storočia celú strechu kostola prekryli pozinkovaným plechom a začiatkom osemdesiatych rokov medeným plechom
Významnejšie vnútorné úpravy kostola sa uskutočnili aj v roku 1932, keď sa zistilo, že v dôsledku zostarnutia drevených trámov nad chrámovou loďou omietka začína opadávať. Trámy vymenili, vnútro kostola obielili a vyzdobili nástennými a stropnými maľbami. Ich autorom bol Mikuláš Štalmach z Liptovského Mikuláša. Jeho maliarska práca vydržala až do 70. rokov minulého storočia, kedy sa rozhodli vymaľovanú klenbu chrámovej lode zakryť dreveným kazetovým stropom. Do kaziet neskôr umiestnili terajšie obrazy svätých od akademického maliara Fera Kráľa
V roku 1948 odviezli farníci na opravu organ. Jeho komplikovaná preprava ich donútila upraviť schodište na chór. K zásadnej zmene schodišťa na chór a na vežu došlo v polovici 50. rokov minulého storočia, kedy výstupný prístrešok so schodmi na južnej strane veže nahradili murovanou prístavbou so vstupom z predsiene. Terajšie železné mrežové dvere, ktoré tento vstup uzatvárajú, vyhotovili v 80. rokoch podľa návrhu akademického sochára Alfonza Gromu. Vtedy zadovážili aj nové kyvadlové dvere medzi predsieňou a chrámovou loďou.
V roku 1999 prebehli rozsiahle rekonštrukčné práce vo vnútri kostola. Spočívali v oprave muriva a podlahy sakristie, oprave omietok v chrámovej lodi, obielení vnútra kostola a osadení železných mreží medzi predsieňou a chrámovou loďou. Následná generálna oprava oplotenia kostola nebola jednoduchá a vyžiadala si sebaobetovanie neveľkého počtu farníkov vo forme stoviek odpracovaných hodín.
(Upravené podľa knižky Koreň Milan: Východná. Kostol sv. Štefana prvomučeníka a ľudia okolo neho. Poprad 1999, Marmota Press. 80 s.)