Изначально в Вейделевке был каменный Покровский храм, построенный взамен деревянной обветшавшей церкви в честь иконы Божией Матери "Смоленская". Построенный в 40-х годах 19 века Покровский храм был трёхпрестольным, центральный престол был освящён в честь Покрова Пресвятой Богородицы, северный придел - в честь великомученика Никиты, южный - в честь первого храма - Смоленской иконы Матери Божией. С приходом советской власти в храме ещё некоторое время совершались богослужения, но в середине 1920-х годов храм окончательно закрыли, а в 1930-е годы здание полностью разрушили. Долгое время Покровская церковь размещалась в деревянном старинном здании, в котором прежде располагалась паровая мельница.
В 1997 году архиепископ Белгородский и Старооскольский Иоанн совершил чин освящения закладного камня на месте строительства нового храма. В 2002 году новый Покровский храм был освящён. Святыней храма является икона блаженной Матроны Московской с частицей мощей. Пять разнокалиберных колоколов (весом от 10 до 100 кг) подарили местные жители, Виктор и Мария Юдины. Колокола были изготовлены литейщиками города Каменск-Уральский.