Cerkiew greckokatolicka pw. św. Mikołaja Cudotwórcy została zbudowana w 1759 r. w miasteczku Uhrynów k. Sokala jako świątynia parafialna. W 1900 r. w Uhrynowie wzniesiono nową, murowaną cerkiew. Starą, drewnianą świątynię nabyła parafia greckokatolicka w Ulhówku k. Tomaszowa Lubelskiego z przeznaczeniem na cerkiew filialną we wsi Tarnoszyn koło Ulhówka. Translokacja cerkwi nastąpiła w latach 1903-1904, zaś uroczystego poświęcenia przeniesionej świątyni - tym razem pw. Narodzenia NMP - dokonano w 1906 r. Do 1947 r. cerkiew w Tarnoszynie służyła miejscowym grekokatolikom, zaś po ich ekspatriacji przez władze komunistyczne przeszła we władanie parafii rzymskokatolickiej w Tarnoszynie. W latach 1947-1960 pełniła funkcję łacińskiego kościoła parafialnego. Po 1960 r., kiedy oddano do użytku nowy, murowany kościół, tarnoszyńska cerkiew została praktycznie pozostawiona własnemu losowi, wskutek czego padła ofiarą licznych kradzieży i aktów wandalizmu. Dwukrotnie ją podpalano, jednak w obu przypadkach ogień ugasili okoliczni mieszkańcy. W ciągu ponad 30 lat egzystencji w stanie opuszczenia cerkiew tarnoszyńska została praktycznie pozbawiona elementów wyposażenia wnętrza. Ucierpiała również bryła świątyni.
W 1994 r. cerkiew została nabyta przez parafię greckokatolicką w Lublinie i przeniesiona do Muzeum Wsi Lubelskiej w celu rekonstrukcji oraz udostępnienia dla potrzeb kultowych i muzealnych. W latach 1997-1998 dokonano montażu bryły architektonicznej.
