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