У селі Новосілка була стара дерев'яна церква. Парафія була дочірньою парафії с. Малі Бірки. У 1901 році канонічну візитацію парафії провів митрополит Андрей Шептицький.

На місці теперішньої церкви, збудованої у 1935 році, раніше стояла дерев'яна церква, яка була спалена у 1917 році. Біля неї був цвинтар, який тепер не діє. Збереглося кілька надгробних пам'ятників. На одному є напис: «Тут похоронений провізор церкви Сусла».

У давнину навосілці мали церкву, але тоді село було в іншому місці, ближче до с. Товсте, на Гіликовій горі простягалося в напрямку лісу. Називалося село Залужжя. У роки набігів татар цс село згоріло. Люди, які переселилися до с. Малі Бірки, зберегли назву (тепер ця частина с Малі Бірки і називається «Залужжя»).

Інша частина людей поселилися за яром, ближче до с. Малі Бірки. Це нове поселення вони назвали Новосілка Гриманлівська. Там люди збудували нову дерев'яну церкву. А у 1935 році спорудили уже й муровану. Парафія до 1946 року належала УГКЦ.

За радянських часів церкву закрила державна влада. Богослужіння відновили у церкві на початку 90-х років XX століття. Тоді ж громад а села конфесійно поділилася на вірних УГКЦ і вірних ПЦУ. Нині у церкві відправляють богослужіння почергово дві громади: греко-католицька (якій належить споруда) і ПЦУ (орендують).

При парафії діють: братство «Апостольство молитви», спільнота «Матері в молитві» і Вівтарна дружина.

Парохи:

• о. Олег Сарабун,
• о. Микола Бурега,
• о. Микола Бибик,
• о. Володимир Рута,
• о. Василь Школяр (з серпня 2001).