Василенко проявил себя во всех музыкальных жанрах: его перу принадлежат оперы и балеты, симфонии, оратории, множество романсов, песен, хоров. Был склонен к эпическому тонусу музыки. Характерен интерес Василенко к русской народной песне, к поэзии Древней Руси. Был замечательным знатоком архаических пластов русской музыки: изучал крюковое пение, образцы которого использовал в Первой симфонии (1906), ранние образцы русского фольклора. В предреволюционные годы увлекся эстетикой символизма. Наиболее яркое произведение, написанное под этим воздействием — симфоническая поэма «Сад смерти» по О. Уайльду (1908). Какое здесь многоцветие оркестровых красок! В этом сочинении Василенко показывает себя одним из лучших мастеров оркестра во всей русской музыке. Не менее интересны его романсы этого периода на стихи Брюссова, Блока, Мирры Лохвицкой.
Последнее имя — еще одно в ряду полузабытых. А ведь она, родная сестра знаменитой Тэффи, возлюбленная Бальмонта, была замечательной поэтессой. Вот что писал о ней В.И. Немирович-Данченко:
Привожу текст одного из романсов Василенко. Он написан на стихи Лохвицкой. Хочется, чтобы те, кто еще с ними не встречались, почувствовали их изящество и прелесть:
Ты лети, мой сон, лети,
Тронь шиповник по пути,
Отягчи кудрявый хмель,
Колыхни камыш и ель.
И, стряхнув цветенье трав
В чаши белые купав,
Брызни ласковой волной
На кувшинчик водяной.
Ты умчись в немую высь,
Рога месяца коснись,
Чуть дыша прохладой струй,
Звезды ясные задуй.
И, спустясь к отрадной мгле,
К успокоенной земле,
Тихим вздохом не шурши
В очарованной тиши.
Ты не прячься в зыбь полей,
Будь послушней, будь смелей
И, покинув гроздья ржи,
Очи властные смежи.
И в дурмане сладких грез,
Чище лилий, ярче роз,
Воскреси мой поцелуй,
Обольсти и околдуй!
В 1907 году Василенко организовал при Императорском Российском Музыкальном обществе общедоступные Исторические концерты и в течение десяти лет дирижировал ими. В том же году стал профессором инструментовки и композиции Московской консерватории, которым оставался до самой смерти. Среди его учеников такие разные композиторы, как Арам Хачатурян и Леонид Половинкин, Александр и Анатолий Александровы, Николай Рославец. О последнем хочется сказать особо. Рославец — один из крупнейших новаторов в истории музыкальной культуры XX века, создатель «новой системы организации звука», техники «синтетаккорда». Начиная с В. Каратыгина, музыкальные критики называли Рославца «русским Шёнбергом».
В послереволюционные годы Василенко увлекся музыкальным фольклором советского Востока, досконально его изучив и внеся большой вклад в развитие музыкальной культуры среднеазиатских республик.