Родился 10 сентября 1912 г. в дер. Алексеевка Елисаветградского уезда Херсонской губернии в семье священника. Рос в Киеве. Отец Н.И. Николенко погиб в застенках советских органов госбезопасности, мать была репрессирована. В 1928 г. поступил в художественную студию Крюгера-Прахова в Киеве, а в 1930 г. перешел в Киевский художественный институт в мастерскую профессора Бойчука, знатока византийского и древнерусского искусства, погибшего в советских лагерях. Художник и иконописец. В 1932 г. уехал из Киева и плавал моряком на международных рейсах. В 1933 г. был арестован и приговорен к 5 годам лишения свободы. В 1933-1939 гг. находился в заключении в лагере. В 1939 г. был снова арестован по обвинению в подготовке вооруженного восстания. Приговорен к расстрелу, с заменой 10-летним заключением. В 1940 г. освобожден по амнистии. Зарабатывал на жизнь, иллюстрируя книги, работал театральным художником. В 1941 г. был призван в армию и, как бывший заключенный, направлен в штрафной батальон. Был несколько раз ранен, попал в немецкий плен и отправлен в рабочий лагерь под Дрезденом. Работал на фабрике в рабочем лагере в Дрездене до окончания войны. После окончания войны избежал принудительной выдачи в СССР. Вернулся к живописи, искал рецепты красок старых мастеров. Преподавал в Русской художественно-промышленной школе в г. Гамбург, организованной Г.Я. Киверовым и А.А. Абрамовым (основная направленность школы – разработка проблем стилистики и техники византийской и древнерусской иконописи и фрески). Одновременно писал иконы для церкви Успения Пресвятой Богородицы в лагере Фишбек (Германия). В 1950 г. с помощью Толстовского фонда эмигрировал в США. В 1951 г. в Фордэмском университете состоялась первая выставка Николенко. Участвовал в выставке византийского искусства в Вашингтоне (1956). Был женат искусствоведе и писательнице Ладе Ростиславовне (урожд. Воиновой) (1915, Петроград - 5 июля 1996, ФРГ). Автор выставки документальных рисунков «Колыма». Участвовал в выставке «Искусство США в 1958 г.» (1958). В 1961 г. состоялась персональная выставка Николенко в музее Атланты, вызвавшая интерес к творчеству художника. В 1962 г. выполнил 104 рисунка для книги «Мифы о героях» - сборника легенд разных народов в пересказе Нормы Лорри Гудрич, изданной «Орион Пресс». В 1969 г. вернулся к изображению природы, к архитектурным пейзажам и сюрреализму. В 1970 г. с женой переехал на постоянное жительство в ФРГ. Оформлял книги А. Галича, А.В. Кузнецова, Дж. Орвелла и др. авторов, выходивших в свет в издательстве «Посев» (Франкфурт-на-Майне). Скончался 12 мая 1975 г. в г. Мюнхен (Германия).