Микола Леонтович народився в дворянській сім'ї мирового судді Павла Парменовича Леонтовича і його дружини Марії Миколаївни, викладачки музики.
Леонтович здобув освіту в Імператорському училищі Правознавства (59-й випуск, 15 травня 1898 р.) у Санкт-Петербурзі. Після його закінчення переїхав до Одеси, а отримавши там природничо-наукову освіту в 1901 році переїздить до Миколаєва.
26 квітня 1901 року відкрив свій домашній акваріум для всіх бажаючих.
У 1903 році стає гласним Миколаївської міської думи.
У 1906 році Леонтович став заступником міського голови. Коли в 1908 році тодішній міський голова Іван Якимович Баптизманський, подав у відставку «у зв'язку з непорозуміннями, що виникли між міським управлінням та податковою адміністрацією міста», виконуючим обов'язки міського голови автоматично став Микола Леонтович.
8 квітня 1909 року міська дума більшістю голосів обрала Леонтовича міським головою на 4 роки. Потім - на наступний термін. Микола Павлович залишався міським головою аж до 1917 року.
Після Жовтневої революції Леонтович піддавався політичним гонінням. 30 травня 1919 року, за рішенням Миколаївської ради робітничих депутатів, Леонтович разом з іншими особами був заарештований за звинуваченням у злочині з постачанням для потреб армії. 11 серпня 1919 року за № 526 у в'язницю прийшов папір з революційного трибуналу. У ній пропонувалося тов. начальнику тюрми «негайно звільнити з-під варти Миколу Павловича Леонтовича, який утримується у ввіреній вам в'язниці, про що зараз же повідомити Трибуналу».
У 1930 році Леонтовича знизили з директорів у наукові співробітники, а в 1935 році - взагалі звільнили. Леонтович влаштувався працювати касиром на ТЕЦ, що тоді будувалася.
28 липня 1937 року Леонтович був заарештований за звинуваченням у зв'язках з контрреволюційно налаштованою інтелігенцією та через участь у військово-офіцерській організації. Точні дата і місце смерті невідомі.
Посмертно, 18 травня 1957 року, справу Леонтовича було переглянуто Президією Миколаївського обласного суду, скасовано та припинено.