Leandro já havia feito parte de duas bandas gospel, o grupo Eldade, como back vocal, e o Grupo Ide, onde foi guitarrista. Com o término do Grupo Ide, Leandro se juntou ao baterista Élbio para exporem as canções espirituais feitas após o encontro religioso, afinal, a banda não havia formas e nem conclusões de como seria feito, apenas a vontade de tocar e os ensaios após a escola dominical renderam muitas canções de cara , como "Na onda", e "Segura a língua". Mas Leandro queria apenas cantar, então Élbio convidou um adolescente de 15 anos para assumir as guitarras, Elias era o guitarrista com grandes influências do lendário e já falecido guitarrista do grupo Catedral Cezar, mas o baixista viria de um outro grande admirador do Catedral: Lucas Rosa, irmão de Leandro que com apenas 14 anos aprendeu a tocar contra-baixo vendo os ensaios do Legionarius.
" Um dia eu fui ensaiar e fiquei sem baixista, o cara sumiu, eu nem lembro quem era, aí meu irmão me falou, eu serei o baixista do Legionarius,mas eu confesso que duvidei, afinal, eu nunca ví o Lucas tocar, mas ele cumpriu, tocou e muito bem, á partir dali ele era sim o nosso baixista." Comenta Leandro relembrando o início da formação.
A primeira gravação feita pela banda foi um mês depois da banda estar montada,sem o Lucas ainda, foram á Macaé e na casa do primo de Leandro, Gustavo Bala, técnico de som, gravaram uma demo com as musicas, Dai glória a Deus, Paz, e Quando eu olho pra você, estas musicas foram tocadas nos carnavais da região dos lagos por Gustavo Bala, mesmo sendo um som de rock. Mas em 2001 faltava sim uma musica para ser tocada nas rádios, então regravaram em estúdio a musica " Dai glória a Deus, que tocou na rádio 88 de Cabo Frio pelo mesmo radialistacque embarreirou " tenho 16" anos mais tarde. "Dai glória a Deus" fez com que Leandro levasse mais á fundo a idéia de que o Legionarius poderia ser a banda que o levaria á muitos lugares e possuir muitas experiências musicais. " Lembro que á caminho da igreja Amai-vos eu escutei Deus me dizendo que meu som não era apenas para evangélicos, na época não entendi, não tínhamos esta idéia de musica como um todo, ou era de Deus ou do diabo, por isso escrevi em " Na onda", ... o diabo que o diga quem é de sua laia... acho que fui um dos primeiros da minha geração a romper as barreiras entre gospel e secular". Comenta Leandro ao falar das motivações e certezas quanto ao que fazer em relação ao Legionarius.
A formação com Élbio, Lucas, e Elias, durou de 2000 á 2002, onde a banda parou suas atividades por 8 meses até encontrarem lugar para ensaiar. Os ensaios eram feitos na igreja Amai-vos,e quase sempre eram embarreirados de tocar e ensaiar pois o som era pesado demais e não fazia parte do sistema de culto tradicional da igreja, mas os poucos espaços que eram cedidos á banda foram bem aproveitados, pois em 2003 com uma nova formação, fizeram o Galpão do Rock, um evento alternativo para que as demais bandas de Rock Cristãs pudessem exercer sua democracia musical. Foram executados 3 Galpões, mas os músicos do Legionarius começaram a variar o que de certa foram enfraquecia a imagem da banda.
A segunda formação foi escalada com Leandro no vocal, Marcelo Cebola no baixo, Allan Ramalho na guitarra, e Hugo na bateria, isto em 2003 quando a cena gospel rock começava a acender em Cabo Frio. " lembro que tocávamos todos os finais de semana, eu não sabia o que era ficar um Sábado em casa", comenta Leandro ao relatar a agenda de programações executadas pelo Legionarius em 2003/ 2004. "Quando entrei para a faculdade em 2004 ainda estava na cena gospel, mas sabia que o som se expandiria para o underground que estava sendo formado na cidade, o professor Chicão era o idealizador, mas eu já estava sem banda outra vez, então através do Pescadores de Almas, uma outra banda gospel, eu conheci Rafael Metal,e como ouvia falar de Gustavo Lage, um luthier que estava disponível para entrar em ação, e por isso reuní esta banda que durou de 2005/2007, ode entrou para a banda Fagner como baixista e com esta formação tocamos em diversos eventos de rock da cidade e gravamos um EP." Comenta Leandro ao falar da trajetória da banda.
Agora de 2008 até 2011 uma nova banda foi montada para dar continuidade ao Legionarius, Saulo, um fâ da banda que hoje toca guitarra com Leandro que está entre os violões e o contra- baixo, e um novo baterista, o Davi Batata, mas devido ao casamento e e o nascimento dos filhos de Leandro, Michael e Nicolas, o Legionarius tem se apresentado pouco, apenas em locais isolados.Em 2011 comemoraram-se 10 anos da banda e o prometido "reunior" da banda ainda não aconteceu pela dificuldade de Leandro ao sair para tocar e ficar com os filhos e esposa, mas para 2012 o Legionarius pode lançar um outro disco blogger, ou o projeto solo de Leandro Machado, sem por fim ao Legionarius, é claro!
