Родился 7 февраля 1956 г. в селе Таскудук Джамбейтинского района Уральской обл. Казахской ССР (ныне в Западно-Казахстанской обл. Республики Казахстан) в семье рабочего. Имя при рождении - Каиргельды. Его отец был казахом, мать происходила из семьи ссыльных немцев.
После окончания средней школы в гор. Чапаеве (также в Уральской, ныне Западно-Казахстанской обл. Казахстана) работал на кирпичном заводе и элеваторе.
С 1974 по 1976 г. прошел срочную службу в рядах Советской армии.
В 1980 г. окончил Саратовское высшее военное авиационное училище летчиков. Освоил пилотирование вертолетов.
В составе Ограниченного контингента советских войск (40-я армия) дважды - с сентября 1984 г. по декабрь 1985 г. и с апреля 1987 г. по май 1988 г. - участвовал в боевых действиях в Демократической Республике Афганистан. Был старшим летчиком отдельной вертолетной эскадрильи, пилотировал машины Ми-6 и Ми-8.
Всего к июню 1988 г. Николай Майданов выполнил в Афганистане 1 тыс. 250 боевых вылетов, его общий налет составил 1 тыс. 100 часов. Лично вывез с поля боя 85 раненых солдат и офицеров, перевез до 1 тыс. десантников и 100 т груза.
Указом Президиума Верховного совета СССР от 29 июля 1988 г. капитану Майданову было присвоено почетное звание Героя Советского Союза ("за успешное выполнение задания по оказанию интернациональной помощи и проявленные при этом мужество и героизм").
В 1992 г. Николай Майданов окончил Военно-воздушную академию им. Ю. А. Гагарина (Монино, Московская обл., ныне Военно-воздушная академия имени профессора Н.Е. Жуковского и Ю.А. Гагарина, Воронеж). В том же году вернулся в Казахстан, где принял командование 157-м отдельным транспортным вертолетным полком в г. Джамбул (ныне Тараз). Однако казахстанская боевая авиация из-за недостатка финансирования тогда практически прекратила полеты. В 1997 г. Майданов принял решение переехать с семьей в Россию, где поступил на службу в авиации Сухопутных войск ВС РФ. Командовал вертолетным полком Ленинградского военного округа, дислоцированным в пос. Агалатово Всеволожского района Ленинградской обл.
В 1999-2000 гг. был командиром 325-го отдельно транспортно-боевого вертолетного полка. Принимал участие в контртеррористической операции в Чеченской Республике.
29 января 2000 г. в районе Аргунского ущелья звено Ми-8, в составе которого находился вертолет полковника Майданова, в ходе высадки десанта попало под плотный пулеметный огонь боевиков. Вертолетчикам удалось вывести машины из-под обстрела и вернуться на базу, однако Николай Майданов получил тяжелое ранение шеи и скончался в кабине вертолета незадолго до приземления, которое провел второй пилот.
Похоронен 2 февраля 2000 г. на Серафимовском кладбище в Санкт-Петербурге.
В марте 2000 г. своим указом исполняющий обязанности президента РФ Владимир Путин присвоил Николаю Майданову звание Героя Российской Федерации посмертно ("за мужество и героизм, проявленные при исполнении воинского долга"). Майданов - один из четырех человек, удостоенных званий Героя Советского Союза и Героя РФ, а также единственный, кому они присвоены за подвиги на поле боя.
Также был награжден орденом Ленина (1988), Красного Знамени (1987), Красной Звезды (1985), "За службу Родине в Вооруженных силах СССР" III степени (1988), Мужества (1999), медалями.
Был женат. Сыновья Рустам и Сергей стали военными.