Метрика першої, дерев’яної, церкви Святителя Миколая (зберігалась із 1742 року) засвідчує час будівництва храму – 1666 рік. Церква належала до числа найзавершеніших пам’яток української монументальної дерев’яної, архітектури. Це була однобанна споруда, пройнята темою центричності. Центральна баня виділялася стрімким злетом вгору. Збудована була церква не з пиляних, а з колотих дубових брусів на дубових підвалинах, під які пізніше був підведений цегляний підмурок. Зруб був обшитий шалівкою в сторч. Хоча церква кілька разів ремонтувалась і перебудовувалась, архітектурних змін вона не зазнала.
Відомо, що в 1789 році церква «вновь перестроена деревянным зданием», а ще була відремонтована в 1761 році.
Єпископ Слобідсько-Український в рапорті в Синод у 1816 році про неї зазначав: «крепкая, только крыша на ней ветхая. Церковнослужители пользуются частью доходов от мельницы церковной получаемых».
Характерним архітектурним прийомом всіх лебединських майстрів того часу був нахил стін всередину приміщення. У Миколаївській церкві він дорівнював 5 сантиметрам на один метр висоти. Вражає уміння майстра використовувати гру світла в приміщенні збудованого ним храму. Ту гру створювали вікна восьмирика і четверика. Вони неабияк підсилювали безкрайність злету будови, надавали просторовій композиції загадковості і безкінечності. В’язка зрубу в церкві була виконана притаманним для лебединських монументальних споруд методом — «без остатку».
Для багатьох будівничих було потребою позначати на висоті споруди якоюсь помітною точкою довжину її будови. В церкві Миколи ця точка – круглі вікна у верхньому восьмирику.
Троє вхідних дверей до храму мали шестикутну форму. Одвірки в них складалися не з двох брусів, як звичайно, а витесані з цілого бруса півметрової ширини. При цьому кут на середині їх висоти зменшений. Тому залом одвірків втрачав чіткість і нагадував лук з натягнутою тятивою.
На одвірках центрального входу можна було прочитати напис: «Во славу святая животворящия… Тройцы Отца и Сына и святого Духа создася храм сей во имя святого Николая Чудотворна При державо благочистивейшия самодержавейшия императрице Екатерине Алексеевне всея России При наследнике ее благоверном Государе цесаревиче й великом князе… Петровиче й государях великих князях Александре Павловиче и Константане Павловиче Благословении преосвященного Явтея єпископа Белгородского й Обоянского» (крапки автор поставив замість слів, які вже не можливо було прочитати).
Із історичних документів храму відомий акт пожертвування церкві вдовою Ганною Юрчихою одного поставу млина, датований 1709 роком.
Площа під спорудою – 800 кв. сажнів. Перший священик церкви – Чижевський, був переселенцем із-за Дніпра (дожив він свого віку в Предтеченській пустині іноком). Дзвіниця Миколаївської церкви знаходилася в окремому зрубі. Найстаріші реліквії церкви: ікона святого Миколая-чудотворця (очевидно, була привезена першими переселенцями), старовинної роботи риза, Євангеліє Московської друкарні 1657 р., дзвін, відлитий в 1660 р. — справжній витвір мистецтва українських майстрів, та кольорова «Тріодь» 1746 р.
Нині існуюча цегляна Миколаївська церква не оштукатурена, вона має компактний в плані об’єм однокупольної церкви з прибудованою дзвіницею, що нагадує форму латинського хреста. До апсиди приблоковані приміщення жертовника і дияконника. Над середньохрещенням, на широкому барабані – купол, бокові приділи перекриті зводами. Дзвіниця теж має хрестові зводи в першому чотирьохгранному і другому восьмигранному ярусах, а вже в третьому ярусі вона завершена сферичним куполом з главкою.
Церква збудована у формах «цегляного» стилю з використанням модернізованих елементів російсько-візантійської і романської архітектури. Центральний і бокові (в рукавах) хрести, оформлені монументальними порталами з напівциркульними профільованими фронтонами над групами приставних (на високих постаментах) колон з капітелями романського типу. Той же ордер, виконаний в наличниках напівциркульних вікон барабана, дзвіниці і декоративних напівколон, що акцентовані рустованими кутами.
Боковини північного та південного приділів мають крупні вікна – трифорії з килевидними архівольтами, що об’єднані неглибокою арочною нішею. Лінія карнизу під куполами церкви і дзвіницею виділена аркатурою. В декорі використані різноманітні варіанти фігурної кладки (сухарики, поребрики, тяги, хрести). В цілому, для будівлі характерне ефектне використання декоративних якостей лицьової цегли, яке надає фасадам яскраву пластичну виразність.
Інтер’єр вирізняється цілісністю та світловою насиченістю простору. В церкві зберігся олійний живопис (в основному зображення святих у повний зріст) і геометричний рослинний орнамент початку ХХ століття.
Миколаївська церква є загальноміською архітектурною домінантою та відіграє важливу роль в композиційній схемі центральної частини міста Лебедина.
Наказом Мінстерства культури, молоді та спорту України від 10.02.2020 №630, Миколаївська церква (вул. Миколаївська, 1) визнано пам’яткою архітектури місцевого значення (охоронний номер 2905-СМ).