Отправной точкой зарождения прихода можно назвать 31 августа 1994 г. Именно этим числом датируется акт о безвозмездной передаче зданий бани и прачечной 1959 г. постройки от ПО «Нафтан» Полоцкому епархиальному управлению. Службы начались в бывшей прачечной после небольшой реконструкции.
Начало строительства храма в честь иконы Божией Матери «Нечаянная Радость» состоялось летом 2008 г., незадолго до юбилейных торжеств Новополоцка (праздновали 50-летие города). Разобрали здание бывшей бани. Вбили 8 металлических колышков. Был отмечен периметр здания будущей церкви, начали копать котлован.
Май 2008 г. – разобрано здание бывшей бани;
Установка первого колышка – 3 сентября 2008 г.;
Первый ковш – 4 сентября 2008 г.;
Первые сваи – 17 февраля 2009 г.;
Начало строительства нижнего храма – 2 апреля 2009 г.;
Установка купола на колокольню – 14 февраля 2011 г.;
Установка креста на купол – 14 февраля 2011 г.;
Установка главного купола – 18 апреля 2011 г.
Храм имеет два престола, верхний и нижний. 8 сентября 2009 г. состоялся первый молебен в нижнем храме мучеников Адриана и Натальи.
14 мая 2011 г. в престольный праздник совершена первая Божественная литургия в нижнем храме мучеников Адриана и Натальи, покровителей семьи.
В ночь с 31 декабря 2011 г. на 1 января 2012 г. совершена первая Божественная литургия в верхнем храме иконы Божий Матери «Нечаянная Радость».