Храм построен на месте пригородной деревни Тростенец. Эта деревня была древним церковным землевладением. Впервые она упоминается в 1503 гoду в cвязи с тем, что супруга великого князя Литовского Александра Казимировича, Елена Иоанновна пожертвовала эти земли Минскому Спасо - Вознесенскому мужскому монастырю. На кладбище д. Тростенец с незапамятных времен была церковь в честь святителя Николая. Средства на строительство выделил один из столичных предпринимателей, нужной техникой и материалами снабжали метростроевцы и предприятия Шабанов — "ЖБИ", "Вторчермет".
Архаичный стиль церкви сохранится и внутри. Свято-Никольский храм г.Минска построен из дерева. Атмосфера храма производит неизгладимое впечатление: cтаринные иконы в киотах, иконостас сделанный из массива мореного дуба, с резьбой выполненной вручную, чугунное паникадило с лампадами. Работы по украшению внутреннего убранства храма и прилегающей территории ведутся и до сегодняшнего дня Кстати, сегодня деревянные церкви почти не возводятся. Подобные храмы сохранились в основном на Полесье (в одном из них — в Пинской епархии служил священником отец настоятеля Алексея). Престольный праздник: 9(22) мая, 6(19) декабря.