Cerkiew w Tyliczu istniała już pod koniec XVI wieku, jednak kształt obecnego budynku został uformowany w czasie przebudowy w 1780 powstał dwa stulecia później po tym, gdy pierwsza świątynia została doszczętnie zniszczona przez pożar. W 1938 wykonano w niej zachowaną do dnia dzisiejszego polichromię. Po Akcji Wisła obiekt został przejęty przez Kościół łaciński.
Cerkiew w Tyliczu jest cerkwią łemkowską, trójdzielną. Ponad przedsionkiem wznosi się wieża o konstrukcji słupowo-ramowej, z drewnianym hełmem i kutym krzyżem. Znacznie mniejsze hełmy znajdują się ponad nawą i nad prezbiterium. Po obydwu stronach nawy cerkwi zlokalizowane zostały dwie kaplice boczne. Podobna konstrukcja występuje jedynie w świątyni w Miliku. Nawę pokrywa dach namiotowy, zaś prezbiterium - kalenicowy.

We wnętrzu zachowała się namalowana w końcu lat 30. XX wieku polichromia. Część wykonanych w jej ramach malowideł (w tym postacie świętych Olgi i Włodzimierza) to kopie ikon z soboru św. Włodzimierza w Kijowie. Starszy jest ikonostas, powstały w XVIII wieku. W latach 80. XX wieku nieznani sprawcy wynieśli z niego część wizerunków, które zostały uzupełnione po 2001. Szczególną cechą ikonostasu w cerkwi w Tyliczu jest wielkość ikon patronów świątyni oraz św. Mikołaja, które, choć umiejscowione w najniższym rzędzie ikon, są znacznie wyższe niż carskie wrota i sięgają rzędu następnego.