В 1800 году в деревне стояло 2 церкви - зимняя Никольская и летний храм Илии Пророка.

В разное время священниками церкви села Ведлозера Ведлозерской волости Олонецкого уезда были Николай Ефимович Скворцов, Михаил Матфеевич Морошкин и Петр Андреевич Малинин; диаконом был Иоанн Иоаннович Беляев, а псаломщикам - Андрей Стефанович Николаевский и Федор Андреевич Пименов.

 В безбожные годы советской власти Ильинская церковь была упразднена и переделана в спортзал, а чуть позднее, в 80-е годы, ее и вовсе разобрали.

Православный приход, после длительного разорения в советский период, возобновился весной 1997 года. Прихожане собирались в здании бывшего детского сада на службы, которые проходили раз в неделю по воскресеньям. В дни православных праздников прихожане уезжали на службы в церкви и часовни района, республики. В июле 2005 года был поставлен Поклонный крест недалеко от места, где стояла бывшая церковь.

27 июля 2005 года ведлозерцы установили Поклонный крест на месте будущего строительства. 30 сентября того же года более 30 ведлозерцев, чтобы участвовать в заливке фундамента церкви. Было куплено 6 мешков цемента, на которые приход собирал деньги в течение долгих 10 лет.

14 июля 2007 года в храме отслужили первую службу. 2 августа 2007 года, в праздник св. Пророка Илии состоялся первый престольный праздник, еще не достроенного храма. В небольшой церкви собралось немало людей, многие стояли на улице. Возглавил Божественную литургию благочинный Центрального благочиния протоиерей Иоанн Тереняк.

В 2009 году строительство храма было окончательно закончено.

Настоятель - иерей Сергий Теплоухов.

Богослужения совершаются 2 раза в месяц.