Onder leiding van bondscoach Richard Páez maakte Maldonado als invaller zijn debuut voor het Venezolaans voetbalelftal op 20 augustus2003 in de vriendschappelijke wedstrijd tegen Haïti (3-2) in Maracaibo. Hij nam tweemaal met zijn vaderland deel aan de strijd om de Copa América: 2007 en 2011. Maldonado, bijgenaamd Gian en El Capo, speelde in totaal 64 interlands en scoorde 22 keer voor Venezuela.