Родился 19 марта 1922 года в селе Шурыгино (ныне Черепановского районаНовосибирской области) в крестьянской семье. Русский. Отец — в годы первой мировой войны — солдат русской армии и полный Георгиевский кавалер, в годы гражданской войны — красный партизан в тылу колчаковской армии.
В 1932 году семья переехала в село Князе-Волконское, Хабаровский край. Там Никитенко окончил среднюю школу, работал в местном авиационном гидроотряде учеником моториста, затем в Хабаровске авиамехаником, одновременно окончил аэроклуб.
В Красную Армию призван в ноябре 1940 года. В 1942 году окончил Бирмскую военно-авиационную школу пилотов, эвакуированную в Ленинск-Кузнецкий с Дальнего Востока. Служил в 5-й запасной авиационной бригаде и в 606-м штурмовом авиационном полку в тылу.
Командир звена 958-го штурмового авиаполка 280-й смешанной Островской авиационной дивизии14-й воздушной армии 3-го Прибалтийского фронта младший лейтенант Николай Никитенко к октябрю 1944 совершил 115 боевых вылетов, уничтожил 12 танков, 41 автомашину, взорвал 6 складов с боеприпасами, потопил катер и две баржи, сбил 1 самолёт противника. Наряду со штурмовой работой проявил себя мастером разведывательных полетов. Из числа боевых вылетов 54 совершены на разведку и аэрофотосъемку позиций врага. В общей сложности сфотографировал 9 тысяч квадратных километров территории[1].
За образцовое выполнение боевых заданий командования на фронте борьбы с немецкими захватчиками и проявленные при этом отвагу и геройство указом Президиума Верховного Совета СССР от 23 февраля1945 года младшему лейтенанту Никитенко Николаю Михайловичу присвоено звание Героя Советского Союза с вручением ордена Ленина и медали «Золотая Звезда» (№ 5339).
К концу войны Н. М. Никитенко совершил 187 боевых вылетов на штурмовку и разведку войск врага, значительно увеличив свой боевой счёт.
Герои Советского Союза: Краткий биографический словарь / Пред. ред. коллегии И. Н. Шкадов. — М.: Воениздат, 1988. — Т. 2 /Любов — Ящук/. — 863 с. — 100 000 экз. — ISBN 5-203-00536-2.
Герои войны. — Таллин, 1984.
Звёзды доблести ратной: О Героях Советского Союза — новосибирцах / сост. Е. Д. Головин, Л. М. Живоглядова. — 2. — Новосибирск: Новосибирское книжное издательство, 1986. — 432 с.
Новосибирцы — Герои Отечества. — Новосибирск: ОАО «НКИ», 2010. — 768 с. — ISBN 978-5-7620-1391-8.
Пронякин К. А. Первые лётчики на Дальнем Востоке России: влетевшие в историю (справочник). К 80-летию Хабаровского края, к 95-летию Гражданского Воздушного флота России и к 100-летию Восточного военного округа. — Хабаровск: ООО «Медиа-Мост», 2019. — 158 с., ил. (Серия: История развития авиации на Дальнем Востоке). — С. 80.
