Гісторыя праваслаўнага храма ў Навасёлках пачалася некалькі стагоддзяў таму назад. Калі канкрэтна была пабудавана драўляная царква ў гонар Казанскай іконы Маці Божай, ніхто не ведае, пісьмовых сведчанняў не засталося. Мясцовыя жыхары распавядаюць, грунтуючыся на ўспамінах сваіх дзядоў, што храм быў спалены ў час Паўночнай вайны са шведамі, магчыма ў 1707–1708 гг., на доўгія гады вёска засталася без царквы.
Мара аб храме ў Навасёлках ледзь не стала рэальнасцю ў самы страшны перыяд гісторыі нашага краю – падчас нямецка-фашысцкай акупацыі ў гады Вялікай Айчыннай вайны. У 1942 г. па ініцыятыве агранома І. Анішчука жыхары сталі ўзводзіць храм, але неўзабаве нямецкая ўлада, даведаўшыся пра гэта, забараніла будаўнічыя работы. Пра факт пачатку будоўлі доўгі час нагадвалі камяні, якія павінны былі стаць падмуркам храма. Да гэтага месца вяскоўцы заўсёды ставіліся беражліва, адчуваючы яго асаблівасць. Менавіта тут, побач з крыжамі, яны збіраліся ў Велікодны дзень.
Навасёлкаўцы былі прыхаджанамі Свята-Успенскай царквы ў вёсцы Паніквы, што за 3 км (у 1962–1988 гг. царква не дзейнічала), але думкі пра сваю царкву не пакідалі людзей. У пачатку ХХ ст. тут пражывала 940 чалавек, якія спадзяваліся на духоўнае жыццё. У 2007 г. зноў пачалася размова пра будаўніцтва новага храма. 21 жніўня 2008 г. быў зарэгістраваны праваслаўны прыход. Будаўнічыя работы пачаліся дзякуючы намаганням настаяцеля царквы ў Паніквах іерэя Аляксея Уладзіміравіча Барзова. Пасля шматлікіх працэдур па падрыхтоўцы праекта ў 2010 г. быў заліты падмурак. З красавіка 2012 г. будаўніцтва храма вялося на ахвяраванні прыхаджан i вернікаў іншых прыходаў Беларусі, пры значнай фінансавай падтрымцы ААТ «Усход-Камянец».
Пасля пераводу айца Аляксея ў іншы прыход Камянецкага благачыння, у Паніквах святаром стаў іерэй Ігар Іванавіч Каляда. Дзякуючы яго энергіі, ініцыятыве і поўнай самааддачы, пачалася асноўная работа па ўзвядзенні храма. Будаўніцтва працягвалася нават тады, калі не хапала сродкаў і ўсё рабілася ў доўг. Айцец Ігар ездзіў у Італію, Грэцыю, Расію, Украіну, каб дастаць святыні, іконы і іканастас для новай царквы.
6 ліпеня 2012 г. на будуемым храме быў узнесены купал з крыжам. У сувязі з гэтай падзеяй каля храма адслужаны ўрачысты малебен, у якім прынялі ўдзел благачынны Камянецкага благачыння протаіерэй Сергій Буркоўскі і настаяцелі суседніх прыходаў.
Будаўніцтва працягвалася 1 год і 3 месяцы. Навасёлкаўская царква пабудавана з цэглы ў спалучэнні двух стыляў: рускага і сучаснага, у плане мае форму крыжа. Асноўны аб’ём накрыты дахам шатровай сістэмы. Вянчаюць будынак пяць цыбулепадобных глаў на барабанах. Побач знаходзіцца аднакупальная званіца з абразамі евангелістаў Марка, Іаана, Матфея і Лукі, размешчаных пад дахам па чатырох баках свету.
29 чэрвеня 2013 г. адбылося доўгачаканае свята – асвячэнне новаўзведзенай царквы ў імя святога апостала Марка, аднаго з чацвярых евангелістаў, аўтара Евагелля ад Марка. Прастол царквы асвечаны епіскапам Брэсцкім і Кобрынскім Іаанам у саслужэнні духавенства Камянецкага благачыння пры вялікім сцячэнні народу. Ордэнам Беларускай Праваслаўнай Царквы ў гонар святога Кірылы Тураўскага за вялікі ўклад у будаўніцтва храма былі ўзнагароджаны: Андрэй Канстанцінавіч Зялёнка, які кіраваў гаспадаркай «Усход-Камянец» у перыяд будаўніцтва, І. Н. Пясенка, А. Л. Савіч.
Храм святога апостала Марка з’яўляецца прыпісным да Свята-Успенскай царквы вёскі Паніквы. У храме знаходзяцца абразы апостала Марка, прывезеныя айцом Ігарам з сабора святога Марка (Італія) і іншыя, падораныя прыхаджанамі. У прастольным крыжы знаходзіцца часцінка чаравічка свяціцеля Спірыдона Трыміфунцкага, прывезеная з сабора святога Спірыдона Трыміфунцкага з вострава Корфу (Грэцыя). Пасля пераводу айца Ігара ў Брэст, настаяцелем назначаны іерэй Сергій Мікалаевіч Скрабец.
Пры храме дзейнічае нядзельная школа, заняткі вядзе прыхаджанка Ірына Громава. З мэтай развіцця ў дзяцей творчых здольнасцяў арганізаваны гурткі прыкладнога мастацтва і харавога спеву. Навучэнцы школы ўдзельнічаюць у канцэртах, прысвечаных святам Вялікадня, Раства Хрыстова і інш. У 2014 г. занялі другое месца на конкурсе малюнка, прысвечанага 700-годдзю з дня нараджэння Сергія Раданежскага.
Матэрыял падрыхтаваны ў 2023 г. Камянецкай цэнтральнай раённай бібліятэкай імя У. М. Ігнатоўскага.
Табольчык Ларыса Мікалаеўна, бібліёграф аддзела абслугоўвання і інфармацыі
- Навасёлкі // Гарады і вёскі Беларусі : энцыклапедыя. Мінск, 2007. Т. 4. С. 67.
- Іконнікава, Л. Навасёлкі: храм на зямлі і ў душы : [аб гісторыі царквы святога апостала Марка] / Людміла Іконнікава // Навіны Камянеччыны. 2014. 19 ліпеня. С. 21.
- Новый приход в Новоселках: [об освящении престола церкви святого апостола Марка 29 июля] // Навіны Камянеччыны. 2013. 10 жніўня. С. 6.