Os primórdios da história da Escola de Música Villa-Lobos nos leva ao ano de 1914, quando as irmãs Suzana, Helena e Silvia Figueiredo, com Celina Roxo, fundaram a Escola de Música Figueiredo Roxo, na Avenida Rio Branco, introduzindo no Rio a moderna técnica de ensino e execução pianística que haviam aprendido em Berlim. Em 1934, por sugestão do compositor Oscar Lorenzo Fernandez, as professoras decidiram fazer a fusão da escola com o Conservatório de Música do Distrito Federal, que se criava, passando a funcionar na Rua do Lavradio.
O Governo do então Distrito Federal idealizou, nos anos 1950, quando já encampara o Conservatório, uma escola popular de ensino musical. Assim, criada pela Lei 703, de 5 de junho de 1952, surgiu a Escola Popular de Educação Musical (EPEMA), que já mantinha em sua estrutura curricular diversos cursos de formação de instrumentistas e matérias teóricas.
Por vários anos itinerante, a escola instalou-se, em seguida, na Rua Frei Caneca, em espaço cedido por um departamento da COMLURB. Após curta passagem pelo prédio do atual Liceu de Artes e Ofícios, na Praça XI, deslocou-se para a Rua São Francisco Xavier, no antigo prédio da Escola Orsina da Fonseca, de onde foi transferida novamente para a Rua 20 de abril, passando a ocupar um velho casarão, que já foi demolido.
Finalmente, nos anos 1960, pertencendo ao então Estado da Guanabara e rebatizada de Instituto Villa-Lobos, fixou-se no sobrado da Rua Ramalho Ortigão, hoje integrante do chamado Corredor Cultural da cidade, um prédio de linhas arquitetônicas Art-nouveau, que fora construído para abrigar alguns dos convidados da Exposição de Paris, em 1910. Em seu percurso de estabelecimento público de educação profissional a escola contou com a dedicação de seus primeiros diretores, professores importantes como Carlos de Almeida, Alda Pereira Pinto, e destaque para Cacilda Borges Barbosa, que foi quem propôs que a nova instituição tivesse o nome do maestro. Juntam-se a estes professores, Florêncio de Almeida Lima, Elza Lakschevitz, Mário Tavares, Nelson Nilo Hack, Milton de Araújo, Alceo Boccino, Humberto Cordovil, dentre muitos.
Com a nomeação de Aylton Escobar para a direção, em 1975, a escola sofreu uma grande reformulação física e institucional. Recebeu a denominação atual e iniciou uma atualização geral do ensino, incorporando as metodologias que mais inovaram o panorama musical da época. Em 1979, a escola recebeu nova direção, de Renault Pereira de Araujo, com a Coordenação Geral de Francisco Fernandes Filho, que deram mais um passo essencial rumo à consolidação da escola enquanto instituição oficial de educação profissional. O que se refletiu na criação do Curso de Qualificação Profissional em Música, em nível de segundo grau, aprovado pelo Conselho Estadual de Educação, em 1981.
Em seguida, sob as direções de Miguel Proença, Wilson Dantas, Ricardo Prado, Cirlei de Holanda e Otávio Brandão, a escola vivenciou um longo período de discussões internas em que se procurou encontrar uma linha de pensamento e atuação, levantando-se inúmeras questões de ordem político-administrativa, artística e pedagógica. Em 1994, sob a gestão de Marcos Vinícius Nogueira, fundou-se a AMAVILLA, Associação de Músicos e Amigos da Escola de Música Villa-Lobos, que reunia todo corpo docente numa associação que organizaria a então "caixinha" dos professores. Em 1999, assume o atual diretor da instituição, o flautista e ex-aluno José Maria Braga, sendo que durante ao longo deste período também assumiram brevemente os diretores Carlos Eduardo Valente, Carlos Belém e Alexandre Guiamares. Em 2020, a AMAVILLA deixa a gestão do Curso Básico, e a concessão é assumida pela ONG Leia Brasil.
Afinada com a orientação que a fez nascer, a Escola de Música Villa-Lobos ainda hoje preserva, como imperativo vocacional, programas de atendimento de massa, visando proporcionar a oportunidade do ensino musical à população fluminense. Seu corpo docente atual tem em torno de 70 professores, entre efetivos e convidados, que atuam nas mais variadas áreas do ensino musical, desenvolvendo currículos tanto de formação básica, para iniciantes, quanto de formação de profissionais de nível técnico. Ao longo dos anos, este corpo docente contou com nomes ilustres, valendo mencionar, por exemplo, Noel Devos, Paulo Moura, Paulo Fortes, Guerra Peixe, Celso Wotzenlogel, Ester Scliar e Maria José Michalsky.
O corpo discente constitui-se de pessoas de todas as faixas etárias e áreas de interesse, que ingressam na escola através de variadas formas de seleção. Alguns nomes que passaram pela escola e deixaram suas marcas no mundo musical são Maximiniano Cobra, Tim Rescala, Tato Taborda, Jorge Versilo, Biafra, Téo Lima, Marcus Vinicius Nogueira, Nelsinho Freitas, Alcides Sodré, Ana Paula Cruz, Jonathan Ferr, Abel Luiz, e Caio Prado.