Родился 28 февраля 1909 года в городе Санкт-Петербурге. С 4 июня 1931 года в рядах Красной Армии, призван по специальному набору Петроградским РВК (город Ленинград). В 1934 году окончил Качинскую военную авиационную школу лётчиков. Служил в строевых частях ВВС, Черниговской военной авиационной школе пилотов, окончил Академию командно-штурманского состава ВВС КА.

С 23 сентября 1942 года капитан Н. М. Веселов в действующей армии. Воевать начал в должности командира эскадрильи 181-го ИАП (19 августа 1944 года преобразован в 180-й Гвардейский ИАП), позже был штурманом полка. В июне 1943 года был тяжело ранен и контужен. С января 1944 года служил в Управлении 235-й ИАД. С февраля 1945 года командовал 180-м Гвардейским ИАП (15-я Гвардейская ИАД). Сражался на Калининском, Сталинградском, Южном, Северо-Кавказском, Воронежском, 1-м Украинском и 4-м Украинском фронтах. Летал на Ла-5.

К 9 мая 1945 года командир 180-го Гвардейского истребительного авиационного полка (15-я Гвардейская истребительная авиационная дивизия, 10-й истребительный авиационный корпус, 8-я Воздушная армия, 4-й Украинский фронт) Гвардии майор Н. М. Веселов совершил 196 боевых вылетов, в 28 воздушных боях сбил лично 11 самолётов противника (в последнем наградном листе говорится о 12 личных победах).

После окончания войны продолжал служить в ВВС. С 18 апреля 1959 года Гвардии полковник Н. М. Веселов - в запасе.

Награждён орденами: Ленина (30.12.1956), Красного Знамени (03.02.1943, 28.03.1944, 22.05.1945, 19.11.1951), Отечественной войны 1-й степени (29.09.1949), Отечественной войны 2-й степени (11.03.1985), Красной Звезды (06.05.1946); медалями, в том числе "За боевые заслуги" (03.11.1944).