De 1.75 meter lange Kléberson debuteerde in 1999 op het hoogste niveau als speler van Atlético Paranaense.[1] Daarmee won hij in 2001 als basisspeler het Braziliaans landskampioenschap. Toenmalig bondscoach Luiz Felipe Scolari nam hem in 2002 vervolgens mee naar het WK 2002. Daar speelde hij vijf wedstrijden, inclusief de met 2-0 gewonnen finale tegen Duitsland.
Manchester United haalde Kléberson bij aanvang van het seizoen 2003/04 voor £6.000.000,- naar de Premier League, maar in Engeland speelde hij zich nooit in de basis. Nadat hij in 2005 voor £2.500.000,- aan Beşiktaş JK werd overgedaan, lukte hem dat in zijn eerste jaar in Turkije wel.[2] In zijn tweede jaar in de Süper Lig bleef zijn aantal competitieoptredens beperkt tot veertien. Daarop ging in Kléberson in 2008 terug naar Brazilië, hoewel zijn contract bij Beşiktaş nog een jaar doorliep. Hij sloot zich in zijn geboorteland aan bij CR Flamengo. Daarmee werd hij in 2009 voor de tweede keer in zijn carrière landskampioen en voor de tweede keer ook in Brazilië. Voor Flamengo was het de eerste titel sinds 1992.
Klébersons spel beviel toenmalig bondscoach Dunga zo goed, dat die hem als reservespeler opnam in zijn 23-koppige selectie voor het WK 2010.