Efter några år i Colo-Colos ungdomssektion började chilenaren sin professionella karriär som fotbollsspelare. Säsongen 1998 debuterade han för de Blanco y Negro. Trots Maldonados korta vistelse i den chilenska toppklubben hann han med att förverkliga en barndomsdröm; att bli ligamästare med Blanco y Negro.
Redan 2000 flyttade Maldonado österut och till den brasilianska ligan för att spela för São Paulo. Efter 3 säsonger i São Paulo värvades Maldonado vidare till Cruzeiro av managern Vanderlei Luxemburgo. (Senare blev Maldonado ihop med tränaren dotter). Under sin vistelse i Cruzeiro upplevde chilenaren karriärens största framsteg. 2003 var han en del av laget då man vann Triple Crown. 2006 skrev Maldonado på för Santos.