У 1834 році (за іншими даними — у 1812) у с. Тростинці греко-католицька громада збудувала церкву. У 1911 році за служіння о. Івана Левицького в селі було збудовано нову церкву, з матеріалу старої церкви збудували дзвіницю. До побудови храму були залучені майстри із навколишніх сіл. Дерев’яні колоди сплавляли річкою Дністер і вже на місці обробляли і укладали під орудою головною будівничого Семена Герасим’юка з Гуцульщини та його помічника о. Івана Шейби. Храм освятили на честь Пресвятої Тронці. Іконостас виготовив у стилі бароко різьбар з Яворова Василь Маглич. Він також виготовив два бічні престоли, горне сідали ще, Царські ворота і кивот. Основними жертводавцями у побудові храму стали жителі села, серед яких особливо активними були родини Балагурів, Білобровків, Шелепків, Протасів.

На місці старою храму парафіяни у міжвоєнні роки хотіли насипати символічну могилу Українським Січовим Стрільцям, але тодішня влада не дозволила цього зробити, а організатори отримали покарання — по 40 буків. У 1939 році село майже вщент вигоріло, але храм вдалося врятувати завдяки деревам, які були висаджені навколо церкви. Тоді було знищено 168 дворів зі всіма господарськими будівлями.

До 1946 року парафія і храм належали до УГКЦ. У 1946—1956 роках — до РПЦ. Пізніше церкву закрила державна влада.

У 1989 році, коли УГКЦ вийшла з підпілля, почалося відновлення знищених радянським режимом освячених місць. Так, у 1989 році за ініціативи Ілька Федорчука та релігійної громади села було насипано символічну могилу Українським Січовим Стрільцям, біля якої у 1990 році після її освячення прийняли присягу на вірність Україні всі дорослі чоловіки с. Тростянці. Також за кошти сім’ї Омеляна і Марії Балагурів у селі збудовано каплицю, пізніше її підтримували в належному вигляді їхні діти: Володимир, Василь, Михайло та Микола. Усі хрести, знищені радянською владою, вже у 1990-х роках були поновлені за ініціативи Ілька Фелорчука, Івана Шеленка, Івана Білобровки, Дмитра Собецького.

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

Парохи:

• о. Волковецький,
• о. Стрембицький,
• о. Теофан Глінський,
• о. Горбачевський,
• о. Лопатицький,
• о. Ангелович (до кінця 1889),
• о. Іван Левицький (з 1890),
• о. Рачинський (1948—1956),
• о. Петро Савіцький,
• о. Ярослав Велиган,
• о. Володимир Колобіжка,
• о. Ярослав Максимлюк,
• о. Мирослав Бричка (адміністратор з 2012).