Перша писемна згадка про церкву датується 1515 роком. Відомо, що, перша дерев’яна церква згоріла у 1836 р., а на її місці у 1848 р. побудовано нову дерев’яну, яка також згоріла від блискавки 14 червня 1891 р. У 1904 р. архітектор Василь Нагірний розробив проект нової мурованої споруди. Нагірний Василь Степанович (11.01.1848 – 25.02.1921) – знаний архітектор, народився на Львівщині. Навчався у Львівській технічній академії (1870 – 1871 pp.) і Федеральній політехнічній школі у Цюріху (1871 – 1875 pp.). Працював у Швейцарії, а з 1882 р. у Львові. Відзначався надзвичайною творчою працездатністю (спроектував і збудував понад 200 культових споруд). Застосовував форми неовізантійського і неоросійського стильових напрямків, неоренесансу і неороманіки. В проектах дерев’яних храмів вживав прийоми народного зодчества. За проектами В. Нагірного збудовані муровані та дерев’яні храми в багатьох селах сучасної Львівщини, Тернопільщини, Івано-Франківщини та республіки Польща. На основі проекту В. Нагірного у 1910 р. за стараннями отця Олексія Гоцького будівництво нової церкви було завершене.

Завдяки жертовності парафіян в новій церкві було зведено два бічні вівтарі. Один жертвували парафіяни селянського братства, а другий – парафіяни шляхетського братства. В храмі були встановлені амвон (казаниця), тетрапод, вівтар, проскомидія. У 1911 р. встановлено каркас іконостасу із образами, які намалював художник В. Павликовський із Самбора із оплатою за працю у розмірі 6700 корон. Першу службу було відправлено 1912 р. у Велику п’ятницю. Нова церква, як і попередні, отримала титул Святої Параскеви. Дослідниця І. Скочиляс стверджує, що протягом XIX початку ХХ ст. чисельність греко-католицьких парохій Перемишльської єпархії коливалася в межах 687-713, а оскільки храмів Св. Параскеви було майже 70, то це означає, що практично кожний десятий з них був названій на честь Св. Параскеви.

В українській християнській традиції відомі три Св. Параскеви, титули яких мали українські храми: Параскева Тирнівська – сербка, народилася в Епіваті (поблизу Силістрії) в середині XI ст., відзначалася великою святістю. Після смерті її останки у 1238 р. були перенесені в Тирново, а у 1641 р. – Ясси. Насьогодні вони зберігаються в Белграді; Параскева П’ятниця великомучениця – народилася в багатій родині, вела аскетичне життя, зазнала тортур за небажання зректися Христової віри. Згодом їй відрубали голову; Параскева Мучениця – постраждала при Антоніні в II ст. Таким чином у Перемишльській єпархії храми, посвячені титулами Параскевії Тирнівської та Параскеви П’ятниції, представлені майже порівну – відповідно 38 і 31. Відповідно зображення Св. Параскеви використовувалося на печатках парафіяльної канцелярії. Зокрема, маємо фрагменти парафіяльних печаток села Уличне 1812 і 1911 років, де є присутнім зображення Святої. На сучасній печатці парафії зображення Св. Параскеви відсутнє, а тільки вказується титул церкви.

У 1939 р. за сприяння пароха Данила Бодревича храм був прикрашений і вивінуваний, а 9 серпня 1936 р. освячений єпископом Йосафатом Коциловським. У 1982 р. церкву Св. Параскеви відреставровано всередині, а у 1996 р. зроблено реставрацію знадвору. Також було збудовано нову дзвіницю-арку, адже до того функціонувала стара дзвіниця (залишилася від попередньої дерев’яної церкви), яка ще існує до сьогодні. Розташований храм у центрі села, що має давню назву "Гора”. Мурована будівля візантійського стилю може вмістити до 2500 людей. За переказами, це була третя за величиною церква у Галичині на початку ХХ ст. У плані храм має вигляд хреста з великою банею посередині та чотирма меншими по боках. Восьмерик її середохрестя вкритий банею з ліхтарем і маківкою. Прямокутні рамена, вкриті двосхилими дахами, прикрашені по кутах восьмибічними пілонами, завершеними ліхтариками з маківками. У середині розписана, має чотириярусний іконостас і три престоли – один головний і два бічні. Посередині звисає гарний великий павук, який при сонячному освітленні виблискує в кольорах кристалів.

Нинішнім настоятелем церкви Св. Параскеви є о. Євген Кохан, який народився на Різдво 1941 р. в Бурштині, тоді Станіславської, тепер Івано-Франківської області. Вступив у Ленінградську духовну семінарію, згодом, через ряд обставин перевівся до Одеської духовної семінарії, котру закінчив у 1965 р. Цього ж року вступив до Московської духовної академії, де у 1967 р. висвятився на диякона, а у 1968 р. на священика. Спочатку парохував у Борщеві (через 2 тижні залишив парохію у зв’язку з браком житла) потім у Мельничах біля Журавна (2 роки) і у 1971 р. перейшов на парохію в село Уличне на якій священикує по сьогоднішній день.

Отже, впродовж становлення та розбудови парафіяльного храму в селі Уличне та діяльності місцевих парохів, церква відігравала провідну роль в організації громадського життя місцевої парафії, яке базувалося на християнських цінностях, а місцеві парохи в часі свого настоятельства зробили вагомий вклад у розвиток освіти та духовної культури серед посполитого люду. В контексті зазначимо, що на сьогодні вже майже викінчений рукопис книги "Історія церковно-релігійного життя в селі Уличне на Дрогобиччині", авторами якої є кандидати історичних наук, доценти Володимир Галик та Юрій Стецик, яка для того щоб бути виданою, чекає спонсорської допомоги з боку усіх небайдужих цінителів історії своєї малої батьківщини й рідного краю загалом.

Володимир Галик кандидат історичних наук