Якщо була парафіяльна школа - була й парафія (належала до Самбірського деканату). Була парафія - був і костел. Напевно, дерев'яний - з чого ще будувати в багатих лісом Карпатах? Напевно, фундований Гербуртами - найбагатшим місцевим родом.
Документи викидують на берег історії ще одну знахідку з хвиль океану невідомого: 1433 рік, згадана дзвіниця отого самого дерев'яного парафіяльного храму. Певно, тоді вона теж стояла окремо - і та, що входить в комплект до храму зараз, теж міститься трошечки осторонь від святині.
Новий храм після руйнації 1498 р. взялися зводити у 1512 р. з цегли (типовий будматеріал для регіонів, бідних природним каменем) - і чомусь в пізньоготичному лаконічному стилі. Скільки будували, не відаю, але знаю, що в 1602 р. в святині встановили дерев'яний головний вівтар. За чотири роки додається й бічний вівтар, присвячений св. Анні, в 1617 р. з'являється третій, вівтар св. Станіслава.
В часи європейської Реформації, наприкінці XVI ст., костел у Новому Місті коротчкий час належав аріанам.
Чотиритомник "ПГіА УРСР" згадує ще й 1614 р. як важливий для будівництва костелу. Саме цей рік був вибитий на райдужній балці храму (сама балка не збереглася). Після 1611 р. біля святині було зведено дерев'яний шпиталь. І шпиталь, і дерев'яна брама костелу згоріли під час великої пожежі Нового Міста у 1625 р. Відбудували їх вже після 1642 р.
Орган в костелі було встановлено вже в 1610 р. Освячення храму і трьох його вівтарів відбулося 21 квітня 1639 р.
Протокол візитації від 1642 р. повідомляє, що при храмі була каплиця Добриницьких, а костел було оточено земляним валом. Сліди того валу можна прослідкувати й понині. Отже, інкастельованість в храму таки прослідковується. Тільки от не допоміг той вал: в 1648 р. костел розграбували козаки, про що було написано на одній з цеглин храму. Начебто кров на стінах після козацього нападу на храм видно було ще й у 1725 р.
Ще до 1721 р. в костелі було встановлено нові бічні вівтарі (св. Станіслава, св. Антонія Падуанського і св. Ядвіги, а також св. Хреста і Богоматері св. Розарію). В 1743 р. Нове Місто відвідав єпископ Вацлав Сераковський, в протоколі його візитації зазначається про спорудження нової дерев'яної дзвіниці та відновлення каплиці Добриницьких, яка тоді отримала титул св. Яна Непомука. Ренесансна каплиця дожила до наших днів.
Єпископ ще раз відвідав храм за 10 років, у 1753 р., коли було повторно освячено костел. мурована дзвіниця прийшла на заміну дерев'яній між 1796 і 1815 рр. Ці дати розбивають на друзки всі надії на те, що ця споруда могла виконувати хоч якісь оборонно-спостережні функції. Не могла. Часи вже були не ті.
З 1746 р. костел став садибою власного деканату, куди входило 13 сіл. З 1785 р. увійшов до Добромильського деканату. У 1796 р. священик Юзеф Лісовський за власні кошти відремонтував вікна та орган у костелі.
В 1870-х. святиню було відремонтовано. Кошти частково надала родина австро-угорського цісаря Франца-Йосифа. У 1875 р. перекрили дах костелу. Нова сигнатурка на даху з'явилася у 1883 р. Для подальшого ремонту потірбні були гроші - і їх збирали у 1884 р. за допомогою лотереї. В Австро-Угорщині тих часів лотереї були можливі лише за погодженням з імператором - і ця теж отримала такий дозвіл.
Храм було ґрунтовно відреставровано в 1889-1890 рр. Роботами керував архітектор Томаш Прилинський (1847-1895). Прилинський був одним з перших спеціалістів у Речі Посполитій, котрйивідмовився від принципів Віоле ле Дюка і намагався відтворити споруди не в єдиному стилі, а дотримувався стилістичного плюралізму. Реставратори намагалися повернути святині первісний вигляд. Саме з того часу походять неоготичні вівтарі, котрі є в костелі зараз - стилізовані під готику вітражі походять з того часу преточнісінько. Всі збережені до того часу інтер'єрні штукенції, всі вітарі та інші артефакти Прилинський замінив на новоробну неоготику - і хто його знає, що втратив храм завдяки такому підходу. Тоді ж було заштукатурено інтер'єр та прибудовано прямокутне приміщення на південь від хорів. Нео-готика була гостромодною, тому старий фронтон з XVIII ст. зняли, замінивши його щипцем, стилізованим в формах північної пломеніючої готики. Так що реальної готики маємо раз - форму вікон, маємо два - нервюрні склепіння в інтер'єрах, які опираються на чотири колони, маємо три - невелику псевдо-оборонну башточку на північному фасаді. Оце й все.
В 1897 р. новоміським костелом зацікавилися історики архітектури - в принципі, це було перше і єдине таке дослідження пам'ятки. Тодішні спеціалісти датували споруду 1527 р. на підставі надгробку, котрий знаходився у храмі (ймовірно, там був похований фундатор святині).
Станом на 1913 р. храм обслуговував понад дві тисячі католиків з 10 навколишніх сіл, а парохом був отець Ян Галушка. (1919-1939 рр. - отець Йосип Будовський).
Велетенське дерев'яне розп'яття з Нового Міста (перша чверть XVI ст.) давно вже є експонатом перемишльського архидієцезіального музею. Шкода - у нашій країні замало сакральних пам'яток такого віку.
Цікавий тимпан костелу зі сценою вознесіння (скульптури - ну чистий тобі романський стиль, взагналі для України найдефіцитніший) теж давно на території Польщі, у Кракові. Про походження тимпану багато сперечалися, хтось з науковців висував гіпотезу, що його привезли у Нове Місто з костелу св. Петра у Перемишлі. Художник і теоретик мистецтв Владислав Лущкевич вважав тимпан витвором народного майстра XVI ст. Коротше, те, що на перший погляд виглядало як чудовий зразок романської пластики, виявилося провінційним барельєфом ІІ половини XVI ст., зразком народного мистецтва. Можливо, автор тимпану був і автором дитячого надгробку того ж часу з костелу в Добромилі.
Навіть після ІІ Світової війни, коли Нове Місто стало радянським селом, костел діяв - завдяки старанням пароха Яна Шетелі (1937-1990 рр.). Це, безумовно, сприяло збереженню пам'ятки.
В храмі є чотири мармурові епітафії місцевих шляхтичів з ХІХ - початку ХХ ст.
