Нинішня церква Покрови Пресвятої Богородиці збудована у другій половині ХІХ століття (1863-75-ті рр.), і замінила дерев’яну Покровську церкву, побудовану ще першими поселенцями Лебедина.
Точний рік її побудови (дерев’яної Покровської церкви) невідомий, але з метрики знаємо, що в 1777 році вона вже потребувала ремонту і була перебудована – «возобновлена в дереве». До ремонту вона простояла не менше 100 років. Площа під спорудою – 480 кв. сажнів.
З духовного заповіту 1678 року відомий священик цієї церкви – отець Леонтій. Служба в ній велась двома священиками. Із церковних стародруків в церкві зберігалися «Служебник» (1743 року) і «Акафіст» (1746 року). Обидві книги друковані в Лаврській друкарні.
В середині ХІХ ст. настоятелем Покровської церкви був отець Максим – один з братів Залеських, до яких під час подорожі на Україну в 1859 заїздив Тарас Шевченко. Поруч з храмом на церковному цвинтарі знаходиться і місце його поховання.
У 1875 за кошти парафіян на місці колишньої дерев’яної церкви була збудована нова цегляна, однобанна, з дзвіницею – Покровська церква. Знаходиться вона на околиці історичного центру міста, на височині лугової заплави річки Вільшанка (тепер це вулиця Покрівська, 44). Стильова єдність з Вознесенською церквою, яка простежується у формах та деталях, дає можливість висловити припущення, що обидві церкви виконані одним автором. Поруч із церквою знаходиться третє міське кладовище – Покровське.
В архітектурному плані, церква являє собою тип тридільного з прибудованою дзвіницею храму, об’ємно-просторова структура якого зберігає традиції української дерев’яної сакральної архітектури.
Церква цегляна, нетинькована (до недавнього часу). Центральний четверик зі світловим підбанником перекрито хрестовим склепінням з розпалубками. У вівтарі та притворі зводи циліндричні, переходять у зімкнуті, з двома великими розпалубками; в дзвіниці – хрестові.
Характерним для будівлі є поєднання класицистичного трактування основних об’ємів з елементами «руського» стилю, що виконані в лицьовій цеглі. Домінуючий у композиції центральний четверик, прямокутний у нижній частині та циліндричний у верхній, завершено ліхтарем з цибулястою маківкою. Церква з південного і північного боків має бічні входи з ганками (первісно були з тридільним аттиком). Вікна другого ярусу підкреслені півциркульними, модельованими в цеглі арками на імпостах.
Дзвіниця, прямокутна в перших двох ярусах, у третьому восьмигранному має високі вікна з лучковими перемичками. Увінчана наметом, в основі якого розміщені кокошники. Роги основних об’ємів акцентовано лопатками, вінцеві карнизи – поясами аркатури і сухариків.
Частково зберігся первісний розпис інтер’єру олійним живописом у вигляді окремих картин: Ісус на усю стіну східної частини вівтаря; у центральному четверику – Покрова у верхній частині східної стіни та парні фігури святих на північній і південній стінах, а також орнаментальний розпис, у т. ч. на арках і склепіннях.
При церкві довго діяла церковно – парафіяльна школа. До церковної парафії відносились хутори: Гарбарі, Дремлюги, Маськи, Барабашівка, Пелипенків. В 1930 в Лебедині закрили всі церкви, в тому числі й Покровську. На початку 1930-х рр. її використовували як склад для зберігання зерна. Наприкінці 1941 вона відновила свою діяльність.
Трагічно склалася доля церкви у повоєнний час. На початку 1960-х рр. під час антирелігійної кампанії, діяльність усіх церков на території Лебедина і району майже припинилася. Покровську церкву передали у володіння міськторгу, який перетворив її склад для зберігання тари. Споруда довго не ремонтувалася, дедалі більше протікав дах. Унікальна пам’ятка архітектури поступово руйнувалася і прийшла у катострофічний стан. В 1986 році від зносу церкву врятували Т.І. Капран та В.М. Лобинцев.
Поновила свою діяльність Покровська церква лише у 2010 році. З того часу завдяки отцю Василю там розпочалися відновлювальні роботи: відремонтовано дах, оштукатурено стіни, проведені внутрішні ремонтні роботи. У квітні 2015 року, Покровська церква отримала в подарунок 5 нових дзвонів. Дзвони виливали за старовинною технологією на одному з заводів України.
Слід сказати, що дзвони є однією з необхідних особливостей православного храму. В чині благословення дзвону сказано: «Нехай усі, хто чує голос його, чи вдень, чи вночі, славлять ім’я Святе Твоє». Православний люд поєднує з церковним дзвоном всі свої урочисті та сумні події. Тому він служить не тільки зазначенням часу Богослужіння, але і виразом радості і смутку.
Наказом Мінстерства культури, молоді та спорту України від 10.02.2020 №630, Покровська церква (вул. Покрівська, 44) визнано пам’яткою архітектури місцевого значення (охоронний номер 2904-СМ).