Дело началось с письма камер-юнкера, статского советника Аполлона Михайловича Редкина, адресованного М.Н. Муравьёву, который в то время занимал должность виленского губернатора. Автор письма просил выстроить православный храм во имя святой Марии Египетской в одном из государственных селений подведомого губернатору края. При этом проситель заранее жертвовал на это строительство 10 тысяч рублей серебром. Просьба жертвователя о том, чтобы храм освятили во имя преподобной Марии Египетской, являлась неслучайной. В смутное, отчаянное время, носившее признаки гражданской войны, требовалось обратиться к таким святым, которые примером своей жизни показали бы путь к выходу из труднейшей ситуации.
Пожертвовать деньги на храм в такое смутное время мог только благородный человек. Аполлон Михайлович Редкин родился в 1807 г. в дворянской семье на Орловщине. Окончил Московский университет. С 1842 по 1847 гг. был орловским вице-губернатором. В отставку вышел в звании камергера и чине действительного статского советника. Всю жизнь занимался благотворительностью. Редкин был знаком с виленским генерал-губернатором Муравьёвым. Знал его исключительную честность. Поэтому он доверил ему деньги без всяких расписок. И не ошибся.
Муравьёв немедленно обратился к митрополиту Иосифу Семашко с сообщением о полученном пожертвовании. И уже 2 июля 1863 г. митрополит вынес на рассмотрение генерал-губернатора предложение построить на пожертвованные Редкиным деньги церковь. Выбор места строительства он предоставил самому генерал-губернатору: либо в Вилейке, либо в селе Собачинцы Лидского уезда. Генерал-губернатор принял решение в пользу Вилейки. Об этом уведомили Редкина. И тот в своём письме Муравьёву 15 сентября 1863 г. сообщил, что уже ознакомился с проектом церкви и что ему он понравился. Представленная смета превысила сумму пожертвования, поэтому Редкину пришлось добавить недостающие полторы тысячи рублей.
Храм был заложен в церковном квартале, рядом со Свято-Николаевской церковью. Чтобы освободить площадку, пришлось снести усадьбу священника Иллариона Выржинковского. Строительство храма закончили летом 1865 г. Освящение состоялось 22 августа 1865 г. О нем сообщали «Виленские губернские ведомости». В частности, сообщалось, что церковь строилась архитектором Полозовым. Храм имел пять башенок и колокольню над западным входом. Его зал рассчитан на 450 человек. Иконы писаны художником Васильевым, а все деревянные работы принадлежат резчику Фендеру. В 9 часов утра в день освящения церкви начался благовест на колокольне нового храма; на площади был выстроен батальон расквартированного в Вилейке Ярославского полка. В 10 часов утра прибыл епископ ковенский Александр. Состоялось перенесение из старой церкви в новую святых мощей. Потом была литургия. В тот же день об этом освящении сообщили телеграммой М.Н. Муравьёву. Последний не замедлил ответить: воздвигнутый храм — лепта в память о тех русских, которые пали при усмирении последнего польского мятежа. Мятеж оказался действительно последним.
Упомянутый художник Михаил Николаевич Васильев (1826-1900) был профессором исторической живописи Санкт-Петербургской Академии художеств. Помимо Вилейки, иконы его кисти украшали соборы Риги, Житомира, посольскую церковь в Париже, Николаевскую церковь в Севастополе. Он принимал участие в работе по росписи храма Христа Спасителя в Москве.
За пожертвование суммы на строительство церкви во имя святой Марии Египетской камер-юнкер Аполлон Редкин был представлен к ордену святого равноапостольного князя Владимира III степени, а архитектор Алексей Полозов — к ордену святой Анны III степени. Именем мецената можно было бы назвать и одну из улиц этого города.
Интересно, что изначально проект церкви не предусматривал часы на колокольне. Появились они по подсказке градоначальника и были установлены за счет прихожан.
Святыни: Ковчег с частицами мощей: свт. Никифора исп. патриарха Константинопольского, свт. Димитрия митрополита Ростовского, свт. Луки исп. архиепископа Симферопольского, вмч. Прокопия Кесарийского, мч. Ореста Тианского врача, прп. исп. Александра Санаксарского, прп. Феодора Санаксарского, прп. Феодора Ушакова, прав. Иоанна Кормянского, мчч. Антония, Иоанна, Евстафия Виленских