Родился 18 (30) марта 1872 года в Москве в семье управляющего имениями. В 1882 году его семья перебирается в деревню Царёвка (ныне Долгоруковский район Липецкой области), но за ними остаётся московская квартира. В книге "Воспоминания" Василенко писал о своих впечатлениях от первой поездки в деревню с матерью: как удивило его кваканье лягушек, шум деревьев и вся сельская округа. "Я приезжал туда с мамашей в конце мая. Мне все там нравилось, начиная с дороги. От Ельца ехали на лошадях, день склонялся к вечеру. По бокам дороги тянулись поля ароматной ржи, цветущей, дышащей медом гречихи; проезжали через темные, покрытые кустарником балки (овраги); в них журчали ручьи, кричали коростели и стонали лягушки. Осторожно спускались к мельничной плотине, где таинственно поблескивала заснувшая река. От всего я был в восторге" (с.44-45).
Учиться был отдан в известную гимназию-пансион Креймана. Серьёзно обучаться музыке начал с 1888 года, стал брать частные уроки у Ричарда Ноха, затем — у Александра Гречанинова (теория музыки), Георгия Конюса (композиция) и Сергея Протопопова (гармония). Но по желанию отца поступил на юридический факультет Московского университета (учился там в 1891—1896 году).
Встреча с П. И. Чайковским оставила большое впечатление, и планы юноши переменились. В 1895 году он, оставив университет, поступает в Московскую консерваторию. В мае 1901 года он её оканчивает с золотой медалью (по классам контрапункта и фуги у Сергея Танеева, композиции у Михаила Ипполитова-Иванова и дирижирования у Василия Сафонова) и путешествует по Турции, Италии, Австрии, Швейцарии, Франции, посещает Германию, Голландию, Норвегию, Египет.
В 1903—1905 годах был дирижёром Московской частной оперы Мамонтова, в 1907 организовал цикл общедоступных «Исторических концертов» и в течение десяти лет дирижировал ими. В том же 1907 году получил место профессора оркестровки и композиции в Московской консерватории, работал на этой должности до самой смерти (с перерывом в 1941—1943 годах). С 1918 года организатор и руководитель общедоступных концертов и концертов-лекций в Москве, в 1925 принимал участие в организации радиотрансляций классической музыки. Совместно с Мухтаром Ашрафи в 1938 году в Ташкенте работал над созданием первой узбекской оперы «Буран». За годы работы в Московской консерватории воспитал ряд известных музыкантов, среди которых А. В. Александров, А. Н. Александров, Н. С. Голованов и др.
Похоронен на Введенском кладбище в Москве.
Ранние сочинения Василенко отмечены влиянием русского фольклора и старообрядческих напевов, с 1906 года прослеживается связь творчества композитора с поэзией символизма (оркестровые пьесы «Сад смерти» и «Полёт ведьм», романсы на стихи Блока и Брюсова), между 1910 и 1920 он начинает интересоваться народной музыкой Востока и уже в советское время неоднократно использует её мотивы в своих произведениях (балеты «Нойя» и «Иосиф Прекрасный»). Его произведения отличаются богатой колористической оркестровкой, яркой, блещущей остроумием и игрой фантазии музыкой. Василенко — автор учебного пособия «Инструментовка для симфонического оркестра» и книги воспоминаний, вышедшей в Москве в 1979 году. За вклад в развитие узбекской музыки композитору в 1939 году было присвоено звание Народного артиста Узбекской ССР, в 1947 году он получил Сталинскую премию.
Написал несколько дополнительных номеров к балету Ц. Пуни «Эсмеральда» в редакции Р. М. Глиэра.