Родился 18 сентября 1923 года в селе Шурыгино ныне Черепановского района Новосибирской области в семье крестьянина. Русский.
Окончил начальную школу. Работал комбайнером.
В ряды Красной Армии призван Черепановским РВК в декабре 1941 года. В боях Великой Отечественной войны с августа 1942 года.
Член КПСС с 1944 года.
Командир расчета орудия 157-го гвардейского артиллерийского полка (74-я гвардии стрелковая дивизия, 8-я гвардейская армия, 3-й Украинский фронт) гвардии сержант Леоненко 23 мая 1944 года при отражении контратаки пехоты и танков противника близ реки Днестр, юго-восточнее пгт Григориополь (Молдавия), прямой наводкой подбил 2 танка, подавил 3 пулемета, 1 орудие и поразил много солдат и офицеров.
5 июня 1944 года награжден орденом Славы 3-й степени.
Гвардии старший сержант Леоненко в том же боевом составе (1-й Белорусский фронт) 8 октября 1944 года в районе населенного пункта Грабув-Залесны (3 км юго-восточнее города Варка, Польша) из орудия ликвидировал 3 пулемета, 1 миномет, а также группу автоматчиков. Затем отсек пехоту от танков, уничтожил пулемет и свыше взвода живой силы.
20 декабря 1944 года награжден орденом Славы 2-й степени.
5 февраля 1945 года близ города Познань (Польша) при отражении контратаки превосходящих сил противника Леоненко остался у орудия один, поджег два танка. Был тяжело ранен, но поля боя не покинул.
31 мая 1945 года награжден орденом Славы 1-й степени.
После войны демобилизован. Вернувшись с фронта, работал в городе Черепаново в «Сельхозтехнике» мастером. В 60-е годы уехал в Талгарский район Алма-Атинской области (Казахстан). Жил в поселке Кок-Тюбе, работал в совхозе «Горный гигант».
Награжденорденом Отечественной войны 1-й степени, медалями.
В Новосибирске имя полного кавалера ордена Славы Николая Максимовича Леоненко увековечено на Аллее Героев у Монумента Славы [56, 288, 418, 601, 932].