Народився 1 грудня 1877 року в селі Монастирок Брацлавського повіту Подільської губернії в сім'ї сільського священика. Раннє дитинство пройшло у селі Шершнях Тиврівської волості Вінницького повіту. Початкову музичну освіту Леонтович здобув у батька, який грав на віолончелі, скрипці, гітарі та деякий час керував хором семінаристів.

У 1887 році Леонтович вступив до Немирівської гімназії. У 1888 році, через брак коштів, батько переводить його до Шаргородського початкового духовного училища, де вихованці утримувалися на повному пансіоні. В училищі він опанував спів по нотах і міг вільно читати складні партії в церковних хорових творах.

1892 року Леонтович вступив до Подільської духовної семінарії в Кам'янці-Подільському, де вивчав теорію музики та хоровий спів, опанував скрипку, фортепіано, деякі духові інструменти, почав обробляти народні мелодії, беручи за взірець обробки М. Лисенка. 1898 року Леонтович закінчив духовну семінарію й вирішив працювати вчителем у сільських школах і водночас самотужки удосконалювати свою музичну освіту. У селі Чукові він організував самодіяльний симфонічний оркестр, який виконував українські мелодії та п'єси російських та українських композиторів. 1901 року він видав перший збірник пісень з Поділля. 1903 року вийшов другий збірник подільських пісень з посвятою М. Лисенкові.

Восени 1904 року залишає Поділля і переїздить на Донбас, де влаштовується викладачем співу та музики у місцевій залізничній школі. Під час революції 1905 року Леонтович організував хор робітників, який виступав на мітингах. Діяльність Леонтовича привернула увагу поліції, й він змушений був повернутися на Поділля, у місто Тульчин, де викладав музику і спів у Тульчинському єпархіальному жіночому училищі для дочок сільських священиків. З 1909 року Леонтович навчається під керівництвом відомого теоретика музики Б. Яворського, якого він періодично відвідує у Москві та Києві.

У той час створив багато хорових обробок, зокрема славнозвісний «Щедрик», а також «Піють півні», «Мала мати одну дочку», «Дударик», «Ой зійшла зоря» та ін. У Тульчині знайомиться з композитором Кирилом Стеценком. 1916 року разом з хором Київського університету виконує свою обробку «Щедрика», яка принесла йому великий успіх у київської публіки.

Із встановленням Української Народної Республіки Леонтович переїздить з Тульчина до Києва, де починає активну діяльність як диригент і композитор. Ряд його творів включили до свого репертуару професійні та самодіяльні колективи України. На одному з концертів великий успіх мала «Легенда» Миколи Вороного в обробці Леонтовича. Після приходу більшовиків Леонтович працює деякий час у музичному комітеті при Народному комісаріаті освіти, викладає у Музично-драматичному інституті ім. М. Лисенка, разом з композитором і диригентом Г. Верьовкою працює у Народній консерваторії, на курсах дошкільного виховання, організовує кілька хорових гуртків.

Під час захоплення Києва 31 серпня 1919 року денікінцями, які переслідували українську інтелігенцію, змушений утікати до Тульчина. Засновує першу в Тульчині музичну школу. 1919—1920 року працює над першим великим симфонічним твором — народно-фантастичною оперою «На русалчин великдень» за однойменною казкою Б. Грінченка. Восени 1920 року в Тульчині відбулися гастролі хорової капели під керівництвом К. Стеценка та Павла Тичини як другого диригента. Під час концертів капели виконувалися твори Леонтовича. В останні місяці життя Леонтович закінчував оперу «На русалчин великдень».

У ніч з 22 на 23 січня 1921 року композитор перебував у свого батька у селі Марківка Гайсинського повіту, де був убитий агентом ВЧК Грищенком, який напросився в хату переночувати, назвавшись чекістом, що проводить боротьбу з бандитизмом. Вранці невідомий пограбував будинок, застреливши Миколу Леонтовича та зв'язавши руки родині композитора. Текст рапорту, що розкриває ім'я вбивці композитора було оприлюднено лише у 1990-х роках. Основу музичної спадщини Леонтовича складають хорові мініатюри — обробки українських народних пісень, які й донині є неперевершеними й виконуються всіма українськими хорами в Україні і діаспорі. Це позначені великим талантом композитора перлини народного мелосу «Щедрик», «Козака несуть», «Дударик», «Із-за гори сніжок летить», «Женчичок-бренчичок», «Гаю, гаю, зелен розмаю» та багато інших. На основі українських народних мелодій Леонтович створював цілком оригінальні самобутні хорові композиції, всебічно художньо переосмисливши їх, надавши їм неповторного звучання. Леонтович був одним з перших серед майстрів української музики, які по-новому інтерпретували фольклор, використовуючи музичні надбання європейської музично-хорової культури. Водночас почерк Леонтовича вирізняється з-поміж інших граничною гнучкістю і природністю руху голосів, ювелірною шліфовкою деталей. Леонтович вдало використав традиції імпровізаційності в творчості українських кобзарів, які кожну нову строфу тексту пісні інтерпретували по-новому. Леонтович застосовував темброву варіантність виконан