Родился 10 апреля 1921 года в городе Кролевец (ныне Конотопский район Сумской области Украины). Окончил среднюю школу. С 28 ноября 1938 года в рядах Красной Армии, призван Кролевецкий РВК. Окончил Чкаловскую военную авиационную школу пилотов (ныне город Оренбург) и был оставлен в ней лётчиком-инструктором.

4 июня 1943 года лейтенант Н. М. Костенко был направлен на должность лётчика в 813-й ИАП. С 25 июня 1943 года приступил к боевой работе на Западном фронте (в составе 215-й ИАД, 1-й Воздушной армии), летая на Ла-5. С 1 октября 1943 года полк проходил переформирование, находясь в резерве Ставки ВГК. С 21 июня 1944 года приступил к боевой работе на 1-м Белорусском фронте (в составе 215-й ИАД, 16-й Воздушной армии). К тому времени старший лейтенант Н. М. Костенко был уже командиром звена. С 5 августа 1944 года воевал на 2-м Белорусском фронте (в составе 215-й ИАД, 4-й Воздушной армии). С 9 сентября 1944 года боевой работы не вёл: полк находился в Резерве СВГК, занимался по плану учебно-боевой подготовки.

В октябре 1944 года старший лейтенант Н. М. Костенко был переведён на должность командира эскадрильи в 263-й ИАП (той же 215-й ИАД), который находился в Резерве СВГК (аэродром Россь). С 12 ноября 1944 года возобновил боевую работу на 2-м Белорусском фронте, продолжая летать на Ла-5. С апреля 1945 года летал уже на Ла-7.

К 9 мая 1945 года командир эскадрильи 263-го истребительного авиационного полка (215-я истребительная авиационная дивизия, 8-й истребительный авиационный корпус, 4-я Воздушная армия, 2-й Белорусский фронт) капитан Н. М. Костенко совершил 165 боевых вылетов, в 27 воздушных боях сбил лично 7 самолётов противника.

После окончания войны продолжал служить на различных должностях в ВВС. С 27 февраля 1975 года полковник Н. М. Костенко - в запасе. Жил в Москве. Умер 26 сентября 2005 года.

Награждён орденами:  Красного Знамени (27.08.1943, 12.06.1945, 22.02.1955),   Александра Невского (27.11.1945),  Отечественной войны 1-й степени (25.09.1944, 11.03.1985), Красной Звезды (12.07.1944, 30.04.1954, 22.11.1973); медалями, в том числе "За боевые заслуги" (20.06.1949, 22.02.1968).