En 1977, la carrière de Lenine commence à l'âge de dix-huit ans quand il se rend à Rio de Janeiro et participe à un festival de musique[2]. En 1982, il sort chez Philips son premier album, Baque Solto, avec son partenaire Lula Queiroga(pt)[3].
Dix ans plus tard, il sort son second album Olho de Peixe, avec le percussionniste Marcos Suzano, puis en 1997 son premier album solo O Dia em que Faremos Contato, avec un mélange de musique électronique, de rythmes du Nordeste brésilien et de samba. En 1999 il sort Na Pressão, puis en 2001, Falange Canibal. Ce dernier album attire l'attention internationale grâce à la participation du groupe américain Living Colour qui accompagne sa chanson O Homem dos Olhos de Raios-X. L'album (DVD) suivant, Cité, paru en 2004 a été enregistré en public à l'auditorium de la Cité de la musique à Paris.
