Leandro Machado 1976. március 22-én látta meg a napvilágot Porto Alegrében, és a helyi Internacionalban kezdte pályafutását. Már fiatalon bekerült a felnőttcsapatba, húszesztendősen debütált a brazil élvonalban, és első évében rögtön három gólt ért el.
A következő esztendőben már sokkal több játéklehetőséget kapott, 19 találkozón lépett pályára, és nyolcszor talált be. Mindennek köszönhetően 1996 elején bekerült a válogatottba is, a selecaóban a január Gold Cupon mutatkozott be Kanada ellen, és első meccsén rögtön gólt szerzett.
Az olimpiára végül nem utazhatott ki, de a bajnokságban tovább folytatta a gólgyártást, az 1996-os pontvadászatban 11 gólig jutott, és a nemzeti tizenegybe is visszakerült. A következő év elején Európába igazolt, a Valencia szerződtette le szezon közben, és Leandróra nem lehetett panasz, hiszen fél idény alatt nyolc gólt szerzett.
Ennek ellenére 1997 nyarán eladták őt a portugál Sporting Lisboának, ahol szintén jól futballozott, és tíz gólig jutott. Az 1998-99-es pontvadászatban egy rövid időre visszatért Spanyolországba, ám a Tenerifében nem tudta azt nyújtani, amit vártak tőle. Miután a klub kiesett az élvonalból, Leandro visszatért Brazíliába, és a Flamengóhoz írt alá, ahol azonban Romário miatt nem nagyon kapott játéklehetőséget. Miután azonban a fő vetélytárs távozott, már Leandrónak is jobban ment a játék, tavaly 11 alkalommal volt eredményes az országos bajnokságban, az idei év elején pedig négy gólt rúgott.
A Dinamo a nyáron szerződtette, és egyelőre itt sem játszik rosszul, a Vorszkla elleni duplája már a negyedik gólja volt a kijevi klub színeiben.