Родился в селе Курдюм Саратовского уезда 30 ноября (12 декабря) 1858 года, в семье священника Лебедева Андрея Васильевича. По окончании Саратовской духовной семинарии в течение двух лет был служителем церкви; затем в 1879 году переехал в Петербург и поступил в Академию художеств. В 1888 году за конкурсный проект железнодорожного вокзала в одном из городов юга России Н. А. Лебедев был удостоен звания архитектора-художника второй степени и награжден поездкой в Италию для ознакомления с архитектурой этой страны.
По окончании Академии художеств, в 1891 году он приезжает в Брянск и поступает на должность архитектора Арсенала. По его проектам восстанавливается ряд крупных цехов, пострадавших от пожара. После реконструкции цехов и их приемки военным ведомством с высокой оценкой, 7 декабря 1893 года Н. А. Лебедев был повышен из губернских секретарей в коллежские секретари.
В 1900 году Лебедеву присваивается очередное гражданское звание титулярного советника.
В конце XIX века Николай Андреевич сблизился с братьями Могилевцевыми при разработке проекта церкви близ усадьбы Могилевцевых у Петропавловского монастыря (ныне известной как Спасо-Гробовская церковь), и в последующем именно Н. А. Лебедев проектирует большинство зданий в Брянске, построение которых финансируют братья Могилевцевы.
Работы Н. А. Лебедева (большинство из них выполнено в русском стиле) отличает умение работать с кирпичом не только как со строительным, но и как с отделочным материалом. Чередуя выступы и впадины, применяя подтеску и шлифовку кирпича, архитектор придавал сооружениям красивый, поистине уникальный вид. Ещё более усиливало рисунок сочетание красного и белого кирпича.
По проектам Лебедева строились здания в Бежице, Карачеве, Орле, в некоторых сёлах Брянского уезда.
В годы гражданской войны семья Лебедевых эвакуировалась в Нижний Новгород. После возвращения, с 1922 года Николай Андреевич преподавал строительные дисциплины в Брянском индустриальном техникуме.
Из числа последних проектов Н. А. Лебедева следует отметить два храма в сёлах Малый Крупец и Малое Полпино, датированные 1926 годом (оба были реализованы, но до наших дней не сохранились).