Родился 17 сентября 1905 г. в деревне Удога Чериковского района Могилевской области в семье крестьянина. Окончил начальную среднюю школу.

В РККА с 1927 г. В 1928 г. окончил Ленинградскую военно-теоретическую школу летчиков. В 1930 г. окончил 2-ю военную школу летчиков Красного воздушного Флота в г. Борисоглебске, в 1935 г. - курсы усовершенствования командного состава при Военной Воздушной академии им. Жуковского.

Служил в ВВС Московского военного округа. Был командиром звена, отряда, а затем истребительной эскадрильи.

Участвовал в национально-освободительной войне в Китае в марте – августе 1938 г. Командовал эскадрильей, а затем истребительной группой. Провел 5 воздушных боев, лично сбил 2 самолёта противника. Награжден орденом Красного Знамени (14.11.38).

После возвращения из Китая майору Николаенко было присвоено воинское звание полковник. Он был назначен начальником авиашколы, а затем командиром 17-й авиадивизии Киевского Особого военного округа.

22 февраля 1939 г. за образцовое выполнение специальных заданий Правительства по укреплению оборонной мощи Советского Союза и за проявленное геройство, полковнику Николаенко Евгению Марковичу было присвоено звание Героя Советского Союза. После учреждения медали "Золотая Звезда" ему была вручена медаль номер 122.

4 июня 1940 г. ему было присвоено воинское звание генерал-майор авиации.

С 1940 г. командовал ВВС Северо-Кавказского военного округа.

Участвовал в Великой Отечественной войне с 1941 г. В начале войны командовал Резервной авиагруппой (10-я сад, 28-я сад, 60-я сад).

С 1 августа 1941 г. по 10 октября 1941 г.генерал-майор авиации Николаенко был командующим ВВС Резервного фронта. В конце 1941 г. Николаенко был назначен командующим ВВС Крымского фронта.

4 июня 1942 г. генерал-майор авиации Николаенко был снят с должности и понижен в звании на одну ступень.

Вскоре полковник Николаенко был назначен начальником Липецкого авиационного учебного центра, основной задачей которого являлось формирование новых (маршевых) авиационных полков на пикирующих бомбардировщиках Пe-2.

17 марта 1943 г. Николаенко вторично было присвоено воинское звание генерал-майор авиации.

В начале февраля 1944 г. пришло распоряжение о перебазировании в Липецк. Радость возвращения была омрачена крушением поезда на подъезде к Куйбышеву. Пострадали двадцать слушателей, которых в тяжелом состоянии доставили в госпиталь.

В 1944 г. приказом наркома обороны Курсы преобразовываются в Липецкую высшую офицерскую авиационную школу ВВС Красной Армии. Вместо учебных классов были созданы кафедры, которые вели не только учебную, но и научную работу. Прием слушателей проводился с экзаменами. Вместо учебных эскадрилий образовывались учебные полки, размещавшиеся в Липецке и Грязях. Имелась смешанная эскадрилья, вооруженная ленд-лизовскими "Аэрокобрами", "Харрикейнами", "Бостонами", транспортными С-47, трофейными "Хейнкель-111", "Мессершмитт-109" и 110.

Начальником школы стал Герой Советского Союза генерал-майор авиации Ерлыкин, а генерал-майор авиации Николаенко убыл на фронт. Он был назначен заместителем командующего 1-й ВА.

20 апреля 1945 г. ему было присвоено воинское звание генерал-лейтенант авиации.

В 1949-50 гг. генерал-лейтенант авиации Николаенко был командующим Дальней Авиацией. В 1952 г. окончил Военную академию Генерального штаба.

С декабря 1955 г. в отставке. Жил в Ленинграде.