Окончил прогимназию в Глухове, гимназию в Полтаве. В течение года учился на медицинском факультете Дерптского университета, затем перешел на историко-филологический факультет, который окончил со степенью кандидата российской истории (1890; тема кандидатской работы: «Критический обзор литературы по истории земских соборов»). Позднее совершенствовал свои знания, слушая лекции профессоров Киевского университета В. Антоновича, В. Иконникова, А. Лазаревского, М.Владимирского-Буданова, публиковал научные статьи в журнале «Киевская старина», был сотрудником этого издания. Работал в Историческом товариществе Нестора-летописца (в 1919 возглавлял его). С 1893 преподавал историю в частной женской гимназии Бейтель, в 1894—1903 — в Фундуклеевской гимназии и Владимирском кадетском корпусе.
Работал в архивах Киева, Харькова, Чернигова и Полтавы, занимаясь историей левобережной Украины, автор публикаций исторических документов. Также специализировался на изучении истории западнорусского права (в том числе магдебургского права на Украине). В 1903—1905 — секретарь Киевского губернского статистического комитета, непременный член киевского губернського комитета попечительства о народной трезвости. Был членом Киевской старой громады, других общественных организаций.
В 1905—1907 редактировал газету национально-демократического направления «Киевские отклики». Сочувствовал революции 1905 года. За нелегальный сбор средств для помощи рабочим Киева и Санкт-Петербурга, поддержку восстания сапёров в Киеве в 1905, связи с революционными деятелями, публикацию в «Киевских откликах» статей «антигосударственного» характера был приговорён к году тюремного заключения с отсрочкой исполнения судебного приговора. В октябре 1908 — июне 1909 отбывал заключение в тюрьме «Кресты» в Санкт-Петербурге. В 1907 экстерном сдал испытания по программе юридического факультета Новороссийского университета (Одесса), с 1908 — помощник присяжного поверенного, с 1913 — присяжный поверенный Одесской судебной палаты (с 1916 — Киевской судебной палаты). Участвовал примерно в 150 судебных процессах.
В 1910 сдал магистерские экзамены по русской истории. С 1910 преподавал на историко-филологическом факультете Киевского университета, с 1911 — приват-доцент, в январе 1913 из-за политической неблагонадежности отстранён от работы в университете (обвинён в пропаганде идей украинского национализма). С 1914 был председателем правления Киевского учетно-ссудного товарищества взаимного кредита.
Был членом Товарищества украинских прогрессистов, в 1910 вступил в Конституционно-демократическую партию (Партию народной свободы), которая выступала за разрешение использования украинского языка в школах, суде, церкви. Однако кадеты были противниками автономии Украины, приверженцами сохранения единой и неделимой России, поэтому членство в этой партии осложнило взаимоотношения Василенко с деятелями украинского национального движения. Был членом Центрального комитета кадетской партии.
Масон. В 1918 — досточтимый мастер ложи Астрея, входившей в состав Великого Востока народов России.
После Февральской революции 1917 Василенко, по инициативе Михаила Грушевского, стал заместителем председателя Центральной рады, но активного участия в её работе не принимал. 27 марта Временное правительство России назначило Василенко попечителем Киевского учебного округа, а 19 августа 1917 — товарищем министра народного просвещения Временного правительства. Был сторонником эволюционного пути формирования украинской системы народного образования, что не соответствовало политике ускоренной украинизации, выработанной I и II Всеукраинскими учительскими съездами и проводившейся украинским Генеральным секретариатом просвещения. Это вызвало острую критику его деятельности на посту попечителя со стороны Центральной рады. Читал лекции по истории Украины и истории украинского права на Высших женских курсах, в Украинском народном университете. Участвовал в издании «Южной копейки». В январе 1918 стал членом коллегии Генерального суда Украинской народной республики (УНР).
30 апреля 1918 гетман Павел Скоропадский назначил Василенко исполняющим обязанности председателя Совета министров Украинской державы. С 2 мая — министр народного просвещения Украины, в июне-октябре — министр просвещения и искусств. С 3 мая по 21 мая 1918 также исполнял обязанности министра иностранных дел. С 30 июля, одновременно, товарищ председателя Совета министров. Являлся председателем Государственного сената. Стремился привлечь на государственную службу специалистов высокой квалификации. В качестве руководителя системы образования и культуры гетманской Украины руководил открытием украинских государственных университетов в Киеве и Каменец-Подольском, Украинской национальной библиотеки, Украинской академии наук, около 50 школ, архива, музея, театра. В мае 1918 вышел из состава ЦК кадетской партии, выступив за создание самостоятельной украинской партийной организации. Был сторонником расширения связей Украины с другими государствами, образовавшимися на территории бывшей Российской империи.
Гетман о своем министре отзывался следующим образом:
После падения Украинской Державы был включён Директорией Украинской народной республики в число генеральных судей, являлся президентом Киевского университета.
После занятия территории Украины советскими войсками отказался эмигрировать. В 1920 был избран академиком Украинской академии наук, руководил работой её социально-экономического отдела, редактировал «Записки» и «Работы» этого отдела. 18 июля 1921 избран президентом академии, однако 27 февраля 1922 под давлением властей был вынужден сложить полномочия. В мае 1922 — апреле 1926 — председатель Товарищества юристов при Украинской академии наук. Преподавал в Киевском институте социально-экономических наук, Киевском кооперативном институте и других высших учебных заведениях.
В сентябре 1923 был арестован по делу «Киевского областного центра действия», обвинён в создании контрреволюционной организации и шпионаже в пользу Польши и Франции. В апреле 1924 приговорён к 10 годам лишения свободы. В его защиту выступили Украинская академия наук и премьер-министр Франции Раймон Пуанкаре. В мае 1924 срок лишения свободы был сокращён в два раза, в ноябре 1924 заключение было заменено высылкой в Оренбург, а в феврале 1925 Василенко было разрешено вернуться в Киев. Продолжа работать в качестве главы социально-экономического отдела Украинской академии наук, председателя Комиссии по изучению западно-русского и украинского права. В последние годы жизни был тяжело болен. Похоронен на Лукьяновском кладбище в Киеве.
Жена — Наталия Дмитриевна Полонская-Василенко, историк, мемуарист. Брат — Константин, член партии социалистов-революционеров, был также осуждён на процессе 1924.
Николай Василенко любил играть на скрипке (известного итальянского скрипичного мастера Николо Амати). Собрал большую библиотеку.
Автор более 500 научных работ, в том числе:
Издал три тома «Материалов для изучения экономического, юридического и общественного строя Старой Малороссии» (Чернигов, 1900—1907). Поместил несколько статей в изданиях И. Д. Сытина, посвящённых крестьянской реформе и Отечественной войне 1812, а также в «Русской истории», редактировавшейся профессором М. В. Довнар-Запольским.
Национальная академия наук (НАН) Украины присуждает премию им. Н.Василенко. В Киеве его именем названа улица. Национальный банк Украины выпустил монету с его изображением. На зданиях НАН Украины, где он работал, Глуховского государственного педагогического института (в нём находилась прогимназия, в которой он учился) и школы в его родном селе установлены мемориальные доски.