Murowana cerkiew w Tylawie została zbudowana w 1787 r. jako greckokatolicka, ok. 1879 r. dobudowano wieżę, co upodobniło świątynię do klasycznej cerkwi drewnianej zachodniej Łemkowszczyzny. Każda część zabytku kryta jest odrębnym dachem i każdą wieńczy kopulasta wieżyczka z pozorną latarnią. Wokół zachowało się kilka kamiennych nagrobków starego cmentarza, nowy założono w sąsiedztwie.
W 1926 r. wierni miejscowej parafii greckokatolickiej zadeklarowali przejście na prawosławie, co zapoczątkowało szereg podobnych konwersji na całej Łemkowszczyźnie. Ruch ten, który objął ostatecznie kilkadziesiąt parafii, zyskał miano schizmy tylawskiej. Po zatwierdzeniu przez władze państwowe powstania w Tylawie filii parafii prawosławnej, świątynia przeszła na rzecz Kościoła Prawosławnego, by po wysiedleniach lat 40. stać się kościołem rzymskokatolickim.
We wnętrzu zachował się czterostrefowy rokokowy ikonostas, wykonany pod koniec wieku XVIII, odnowiony i częściowo przekształcony w 1908 r. Na parapecie chóru muzycznego zachowało się malowane przedstawienie Chrztu Rusi z 1908 r. Zdobiona posadzka zabytku pochodzi z XVIII w., natomiast ławki datowane są na połowę XVII w. Przeniesione tu zostały z kościoła rzymskokatolickiego w Iwoniczu.