Valdez stroomde in 2000 door vanuit de jeugd van Club Atlético Tembetary in eigen land. Hiervoor speelde hij één jaar in het eerste elftal. Daarop haalde Werder Bremen hem naar Duitsland. Hij speelde vier jaar met de club in de Bundesliga. Valdez tekende voorafgaand aan het seizoen 2006/07 vervolgens een vierjarig contract bij competitiegenoot Borussia Dortmund, waar hij in april 2009 bijtekende tot de zomer van 2012.
Na passages bij Hércules CF en Roebin Kazan tekende Valdez in augustus 2012 een eenjarig huurcontract bij Valencia CF, met optie tot koop voor om en bij de drie miljoen euro. Valencia CF lichtte de aankoopoptie in zijn contract in februari 2013, waardoor Valdez tot juni 2015 verbonden zou zijn aan de Spaanse club.[2] Hij speelde in werkelijkheid geen wedstrijd meer voor de Spaanse club, die hem een jaar later overdeed aan Al-Jazira Club. Dat verhuurde Valdez in het seizoen 2013/14 weer aan Olympiakos Piraeus.
Valdez debuteerde op 8 juli 2004 tegen Costa Rica in het Paraguayaans elftal, nadat hij een jaar eerder met een nationaal jeugdteam had deelgenomen aan het WK 2003 Onder-20. In 2004 was Valdez met Paraguay actief op de Copa América. Zijn doelpunt in het kwalificatieduel tegen Venezuela in oktober 2005 was doorslaggevend voor Paraguays plaatsing voor het WK 2006. Vier jaar later maakte hij ook deel uit van de nationale selectie op het WK 2010. Op beide WK's kwam Valdez in alle wedstrijden van Paraguay in actie, waarvan acht van de negen keer als basisspeler.