Nazwa Horostyta wywodzi się od chworosta czyli zarośniętego uroczyska. Pierwsza wzmianka o istnieniu cerkwi w Horostycie pojawiła się w introdukcji wystawionej w 1521 r. przez Iwana Sopoćkę, dziekana brzeskiego, który z upoważnienia biskupa włodzimiersko-brzeskiego wprowadził księdza Ignatija Sergejewicza na probostwo opolskie „Okromie togo podaju kaplicu w siele Chorostyty, siemuż otcu Ignatiju Siergiewiczu fundacji ich miłosti panow Koptiow. Pri niejże i wołok dwie gruntu nadleżaszczich do tojże kaplicy chramu założenija Czesnego Kresta”. Należąca do parafii w Opolu wieś Chorostyta, w 1521 r. otrzymała cerkiew pw. Podwyższenia Krzyża Pańskiego, nad którą administrację sprawował opolski proboszcz ks. Ignacy s. Sergiusza. Fundatorem świątyni był dworzanin Zygmunta Starego Michał Wasilewicz Kopeć, marszałek hospodarski i pisarz ruski. Był on także doradcą i rzecznikiem spraw ruskich w kancelarii Wielkiego Księstwa Litewskiego. Po śmierci marszałka dobra opolskie wraz z Chorostytą ostatecznie przechodzą w posiadanie Fedora, Iwana i Wasyla Kopciów.
Samodzielna horostycka parafia powstała pod koniec XVII wieku. W 1699 r. właściciele majątku Opola Kopciowie ufundowali nową drewnianą, jednokopułową cerkiew pokrytą gontem. Kronikarz z pierwszej połowy XVIII wieku wymienił trzy krzyże na dachu świątyni: nad babińcem, nad prestołem i na kopule w centralnym punkcie gontowego dachu nad nawą. W latach 1793-1794 horostycka cerkiew poddana została gruntownej renowacji, dobudowano wówczas dwie zakrystie do przebudowanego prezbiterium. W 1848 roku przeprowadzono generalny remont świątyni. Przykryto nawę i prezbiterium wspólnym dwuspadowym dachem oraz zlikwidowano ścianę dzielącą prezbiterium od nawy, otwierając w ten sposób salowe wnętrze. Przeprowadzono wymianę elewacji i renowację polichromii. W 1861 wybudowana została drewniana dzwonnica przykryta gontem. Zawieszono w niej cztery dzwony, z których największy ważył 5 pudów. Rozwój i środki materialne parafia zawdzięczała utworzeniu przez Stanisława Szlubowskiego cukrowni w 1843 r., która stanowiła wyposażenie folwarku Horostyta. Folwark ten w drugiej połowie XIX wydzielono z dóbr opolskich i przekształcono w samodzielny. W tym okresie postawiono w folwarku w Horostycie dwór, gorzelnię, wiatrak i cegielnię. Nowym właścicielem posiadłości w Horostycie był Bronisław Deskur, który był czołową postacią w powstaniu styczniowym. W cerkwi w Horostycie miała miejsce przysięga Deskura i jego towarzyszy na wierność Polsce. Po klęsce bitwy o Radzyń Podlaski polegli powstańcy zostali pochowani w katakumbach obok cerkwi w Horostycie, zaś major Bronisław Deskur wraz z rodziną wyjeżdża do Lwowa. W 1864 roku folwark w Horostycie przejmują Hankiewiczowie. Wychowany w folwarku w Horostycie ks. Roman Hankiewicz był proboszczem parafii w latach 1903-1915.
Od 1875 r. parafia została włączona do prawosławnej eparchii chełmskiej i należała do drugiego okręgu dekanatu włodawskiego. W tym okresie dokonano renowacji świątyni, w 1880 r. wstawiono nowy ikonostas i dobudowano pritwor. Jednym z hojnych darczyńców w latach 90. XIX w. był M.I. Iwanow, kupiec z Moskwy, fundator m.in. cerkwi w Suchawie. Kosztowny remont za sumę 1401 rubli finansowali sami parafianie. Architektem tegoż remontu był inżynier Orłowski zaś wykonawcą Antoni Biełecki. Wstawiono nowy prestoł i żertwiennik według tradycji prawosławnej. Poświęcenia cerkwi dokonał Dziekan Włodawski ks. Jan Plutinski, późniejszy proboszcz parafii w Lubieniu.
W 1915 roku społeczność horostyckiej parafii została wywieziona w głąb Rosji w tzw. bieżeństwie. Cerkiew wówczas była otwierana sporadycznie, 1-2 razy w roku, a obsługiwał ją mnich z Jabłecznej lub kapelan stacjonujących w pobliżu wojsk frontowych. W 1917 roku cerkiew została zamknięta. Formalna decyzja administracyjna o otwarciu cerkwi w Horostycie zapadła na początku 1923 r. Tak późne umocowanie urzędowe było przyczyną późniejszego niedostatku materialnego kleru, gdyż przynależne parafiom zasoby ziemi zostały już rewindykowane lub po prostu rozkradzione. O umieszczeniu Horostyty w tzw. dozorze cerkiewnym zadecydował upór wiernych i miejscowego kapłana. O wyrobieniu społeczno-kulturowym tutejszej ludności może w pewnym sensie świadczyć powstanie filii „Ridnej Chaty” już pod koniec 1919 roku. W okresie międzywojennym administracja państwowa szacowała liczbę wiernych w całej parafii Horostyta na 5 643 osoby. Trudna sytuacja materialna w Horostycie i parafiach sąsiednich wynikała zarówno ze zubożenia wiernych, jak i z dofinansowania konkurencyjnych parafii neounickich np. we wsi Hola.
W 1947 r. na skutek wysiedlenia ludności prawosławnej w akcji „Wisła” cerkiew została zamknięta, a Starostwo Powiatowe we Włodawie wydało zakaz tworzenia placówki. Tuż przed zawieszeniem działalności duszpasterskiej, gdy parafią administrował ks. Konstanty Stachowski, następca ks. Teodozjusza Minczakiewicza, mieszkało w Horostycie około 300 wiernych, a w całym dekanacie włodawskim było 36 200 prawosławnych i cztery czynne cerkwie. Latem 1953 r. erygowano parafię prawosławną w Horostycie z filią w Holi i włączono ją do dekanatu lubelskiego. Proboszczem parafii został ks. Włodzimierz Białomyzy. Od 1959 r. do 2003 r. funkcję proboszcza pełnił ks. Włodzimierz Chodak. Od 2003 r. proboszczem jest ks. Tomasz Łotysz.
Obecny wystrój świątyni nawiązuje do tego z przełomu XVIII i XIX w. W latach sześćdziesiątych parafia w Horostycie wraz z filią w Holi liczyła 360 wiernych. Stan ten utrzymał się do końca lat 70. XX wieku. Obecnie parafia liczy ok. 150 wiernych.
Staraniem ordynariusza Prawosławnej Diecezji Lubelsko-Chełmskiej abp. Abla oraz proboszcza parafii o. Tomasza Łotysza w 2006 r. odremontowana została cerkiew parafialna w Horostycie. Cerkiew poddana została generalnej restauracji, całą świątynię podniesiono o 70 cm i osadzono na nowych podwalinach i podmurówce, wymieniono elewację, podłogę i sufit. W 2007 roku przeprowadzony został remont dachu cerkwi, wymieniono gont, wykonano renowację i wzmocnienie więźby dachowej. W tym roku została również odremontowana dzwonnica, którą podniesiono i osadzono na nowym fundamencie.
W latach 2006-2021 poddane zostało restauracji zabytkowe wyposażenie ruchome cerkwi. Pracami konserwatorskimi objęto ikonostas (XIX w.), osiemnastowieczne feretrony, boczne kioty z ikonami z 1740 roku, oraz późnogotyckie ikony Podwyższenia Krzyża Świętego, Ukrzyżowania, Narodzenia i Zaśnięcia Matki Bożej. Wielkim osiągnięciem konserwatorskim i estetycznym było przywrócenie dawnego wyglądu osiemnastowiecznym ikonom Matki Bożej z Dzieciątkiem z lewostronnym kiocie oraz Pantokratora w prezbiterium.
W latach 2018-2021 horostycka cerkiew ponownie poddana została gruntowej renowacji. Odrestaurowano polichromię oraz stolarkę okienną i drzwiową, wymieniono elewację i podłogę w świątyni i dzwonnicy, wykonano nową instalację elektryczną i alarmową. Renowacja obejmowała również zabytkowy parkan.
Za wyróżniającą się realizację konserwatorską oraz za kompleksowe prace restauratorskie w cerkwi w Horostycie Parafia Prawosławna pw. Podwyższenia Krzyża Pańskiego otrzymała w 2021 rok Laur Konserwatorski.
Uwieńczeniem prac renowacyjnych była konsekracja cerkwi w Horostycie 26 września 2021 r. (-)
