Według tradycji, cerkiew stoi w miejscu poprzedniej, zakupionej na terenie Zakarpacia i przeniesionej tu przed 1792 r. Budowano ją wokół starej cerkwi, a gdy była gotowa, poprzednią dopiero rozebrano.
Orientowana, drewniana, konstrukcji zrębowej, trójdzielna. Prezbiterium kwadratowe z zakrystią od północy. Szersza nawa, babiniec szerokością zbliżony do prezbiterium a wysokością do nawy. Do babińca przybudowany od zachodu maleńki przedsionek. Na zdjęciu z 1978 r widać, że tego przedsionka jeszcze nie było. Wszystkie ściany pobite gontem.
Dachy kryte blachą. Nad prezbiterium i babińcem trójpołaciowe, nad nawa czterospadowy. Nad prezbiterium i nawą blaszane hełmy, pseudolatarnie z ostrosłupowymi blaszanymi daszkami i maleńkie, blaszane makowiczki. Nad babińcem, w zachodniej części taka sama makowiczka, jak nad pozostałymi zwieńczeniemi, umieszczona niemal wprost na kalenicy (podczas budowy cerkwi nie zdążono wybudować trzeciej kopuły). Na wszystkich makowiczkach żelazne krzyże, ozdobione w zakończeniach ramion barwnymi szkiełkami.
Podczas II wojny światowej zostały poważnie uszkodzone dach i ściany. Jeden pocisk zniszczył cały róg cerkwi i wywołał pożar, w wyniku którego spłonął ikonostas. Podczas wojny zginęły też wszystkie księgi i przybory liturgiczne. W 1949 roku cerkiew przeszła pod władanie kościoła rzymskokatolickiego. W latach 1952-53 wyremontowana przez Łemków, którym udało się uniknąć wysiedlenia. Wkrótce potem lokalne władze nakazały rozbiórkę cerkwi z przeznaczeniem materiału na budowę garaży w POM-ie w Miejscu Piastowym. Gdy przyjechali traktorami robotnicy z POM-u, mieszkańcy Olchowca nie dopuścili ich do cerkwi.
Parafia greckokatolicka pw. Przeniesienia Relikwii Świętego Mikołaja w Olchowcu została reaktywowana w 1991 roku dekretem biskupa Jana Martyniaka. W 1996 biskup Kazimierz Górny, ordynariusz Diecezji Rzeszowskiej oficjalnie zwraca świątynię wspólnocie greckokatolickiej.
W miejsce spalonego ikonostasu, w roku 1989 cerkiew otrzymała ikonostas pędzla Andrzeja Stefanowskiego z Zielonej Góry. Zamontowano go prowizorycznie na konstrukcji z drewnianych listew. W 1999 ikonostas Stefanowskiego przekazano do nowej cerkwi w
Gajach (przysiółek Hruszowic) a tutaj zestawiono dwurzędowy ikonostas z ikon przekazanych przez Muzeum w Łańcucie, a pochodzących z nieistniejących świątyń w Leszczawce i Ruszelczycach. Jest tylko rząd Deesis i ikony namiestne. Wrota carskie oryginalne, diakońskie wykonano współcześnie.
Droga do cerkwi prowadzi przez stary, unikalny, kamienny most. Na przycerkiewnym cmentarzu zachowane kamienne nagrobki, z tego dwa przywiezione tu z Brusna.
Msze w cerkwi w niedziele i święta o godz. 10:15.