Родился 13 мая 1921 года в селе Широкое (ныне посёлок Криворожского района Днепропетровской области, входит в Широковский поселковый совет). Окончил среднюю школу. С 25 ноября 1939 года в рядах Красной Армии, призван Пологовским РВК (Запорожской области). В 1941 году окончил Качинскую военную авиационную школу пилотов и был направлен для прохождения службы в 161-й РЕЗАП Западного военного округа. В декабре 1941 года был направлен в 195-й ИАП, который в Учебно-тренировочном центре Ленинградского фронта (город Череповец) проходил переформирование. С 11 января 1942 года в 22-м ЗИАП Московского военного округа (город Кинешма, Ивановской области) осваивал английский истребитель "Харрикейн".

С 11 марта 1942 года сержант Н. Н. Клименко в действующей армии: в должности пилота 195-го ИАП. Воевать начал на Калининском фронте (в составе ВВС 3-й Ударной армии), летая на "Харрикейне". С 4 мая 1942 года боевой работы не вёл: на аэродроме Летняя переучивался на американский истребитель "Киттихаук". С 5 июня 1942 года воевал уже на Карельском фронте (в составе ВВС 32-й Армии), летая на "Киттихауке". Участвовал в обороне Карелии и Заполярья. Действовал на Мурманском и Кандалакшском направлении (со 2 по 8 августа 1942 года на короткий период полк был передан в состав ВВС 26-й Армии). К 20 августа 1942 года младший лейтенант Н. Н. Клименко совершил 32 боевых вылета, в воздушных боях сбил лично 2 и в составе группы 5 самолётов противника.

С 20 декабря 1942 года полк действовал в составе 259-й ИАД, с 25 марта 1943 года - уже 324-й ИАД (7-й Воздушной армии). С 10 мая 1943 года боевой работы снова не вёл: полк проходил очередное переформирование (на аэродроме Мончегорск), переучивался на истребители Як-7Б, Як-9 и ЛаГГ-3. С 3 сентября 1943 года возобновил боевую работу (в составе 7-й Воздушной армии), летая на Як-7Б и Як-9. Действовал в основном на Кандалакшском направлении, прикрывал с воздуха Кировскую железную дорогу на участке Апатиты - станция Кереть, сопровождал бомбардировочную и штурмовую авиацию, вёл воздушную разведку.

К апрелю 1944 года был уже лейтенантом, заместителем командира и штурманом эскадрильи, совершил 221 боевой вылет и провёл около 20 воздушных боёв. С мая 1944 года исполнял должность командира эскадрильи. В июне 1944 года в ходе Свирско-Петрозаводской операции действует над Свирью, прикрывал войска 70-й морской стрелковой бригады и 3-й бригады морской пехоты в ходе Тулоксинской десантной операции. В октябре 1944 года участвовал в Петсамо-Киркенесской наступательной операции.

К началу ноября 1944 года командир эскадрильи 195-го истребительного авиационного полка (324-я истребительная авиационная дивизия, 7-я Воздушная армия, Карельский фронт) старший лейтенант Н. Н. Клименко совершил более 260 боевых вылетов, провёл около 30 воздушных боёв, сбил лично 6 и в составе группы ещё 6 самолётов противника.

14 ноября 1944 года полк был исключён из действующей армии и боевой работы больше не вёл. В январе 1945 года вошёл в состав ВВС Московского военного округа.

После окончания войны продолжал служить на различных должностях в ВВС. С 26 июля 1954 года майор Н. Н. Клименко - в запасе.

Награждён орденами: Красного Знамени (04.04.1944, 10.07.1944), Отечественной войны 1-й степени (14.12.1942); медалями.