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

У 1887 році Леонтович вступив до Немирівської гімназії. 

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

1892 року Леонтович вступив до Подільської духовної семінарії, де вивчав теорію музики, хоровий спів у Є.Богданова - вихованця навчальних класів Петербурзької придворної капели, та І.Лепехіна, диригента чоловічого хору в Кам'янці-Подільському. У семінарії Леонтович опанував скрипку, фортепіано, деякі духові інструменти, почав обробляти записані у селі Білоусівці Брацлавського повіту, куди переїхали батьки, народні мелодії, беручи за взірець обробки М.Лисенка, які були в той час дуже популярними. У семінарії нерідко керував хором семінаристів, у виконанні якого вперше прозвучали його обробки пісень "Гандзя", "Ой чия ж то причина, що я бідна дівчина". 

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

1901 року він видав перший збірник пісень з Поділля. 

1903 року вийшов другий збірник подільських пісень з посвятою М.Лисенкові. 

У 1904-1905 роках під час літніх канікул Леонтович складає при Петербурзькій придворній капелі іспити на звання регента хору. 

Восени 1904 року залишає Поділля і переїздить на Донбас, на станцію Гришине, де влаштовується викладачем співу та музики у місцевій залізничній школі. 

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

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

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

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

Під час захоплення Києва 31 серпня 1919 року денікінцями, які почали переслідувати українську інтелігенцію й шукали Леонтовича, щоб його заарештувати, змушений утікати до Тульчина. Засновує першу в Тульчині музичну школу. 

1919-1920 року працює над першим великим симфонічним твором - народно-фантастичною оперою "На русалчин великдень" за однойменною казкою Б.Грінченка. 

Восени 1920 року в Тульчині відбулися гастролі хорової капели під керівництвом К.Стеценка та Павла Тичини як другого диригента. Під час концертів капели виконувалися твори Леонтовича. В останні місяці життя Леонтович закінчував оперу "На русалчин великдень". 

У ніч з 22 на 23 січня 1921 року композитор перебував у свого батька у селі Марківка Гайсинського повіту, де був убитий невідомим, який напросився в хату переночувати з метою пограбування.