Valdez started his career with Atlético Tembetary, progressing through their youth system to the first-team squad where he made his debut at the age of 16 in Paraguayan División Intermedia in 2000.

In 2001, he was scouted to Germany's Werder Bremen II, where he scored 15 goals in 30 Regionalliga Nord appearances in his second season before joining the club's first-team.

During his years at Werder Bremen, Valdez had his appearances limited due to competition from teammates Aílton, Angelos Charisteas and both Miroslav Klose and Ivan Klasnić, who were the Bundesliga's top striking duo at the time.

Valdez left Werder Bremen in August 2006 to join fellow Bundesliga side Borussia Dortmund for a fee of €4.7 million on a four-year contract, where he was given the number 9 shirt.

After an impressive performance at the 2010 FIFA World Cup with Paraguay, Valdez joined La Liga side Hércules for €3.5 million on a three-year contract, where he partnered with French striker David Trezeguet.

Valdez played from 2015 to 2016 with American club Seattle Sounders FC in Major League Soccer, scoring in the playoffs and winning the MLS Cup in his final season.

[9] Valdez stated that before he left to Asunción to join Atlético Tembetary, he endured depression after the death of his 13 year old cousin who was like a brother, and began consuming cane liquor, a whiskey which was 50 cents per liter, and confessing that he was once almost an alcoholic.

[10] Aged 15, Valdez left his home and family to move to Ypané when he joined the Youth Academy of Atlético Tembetary, and eventually made his first-team debut in the Paraguayan División Intermedia in 2000.

[7] Jürgen Born, chairman of the board or management of German Bundesliga club Werder Bremen and who worked for Deutsche Bank in Latin America, stated that he saw a "madman who never stopped running", remembering youth games in Ypané.

His performances earned him a call-up to the first-team from manager Thomas Schaaf, where Valdez debuted in the 2002–03 Bundesliga in a 1–0 home loss to Energie Cottbus 22 February 2003, where he was substituted onto the field in the 82nd minute for Christian Schulz.

[28] In the 2003–04 DFB-Pokal final on 29 May, Valdez was substituted onto the field for Ivan Klasnić in the 87th minute of the 3–2 win against Alemannia Aachen, as Bremen were crowned champions.

[102] On 3 November, Valdez scored in injury time to complete Valencia's 2–0 victory over Atlético Madrid, inflicting the capital side's first defeat of the season.

[105][106] Wearing the number 9 shirt, Valdez made his first appearance for Al Jazira in a 1–0 away victory against Al-Shaab in a 2013–14 UAE Arabian Gulf Cup tie on 3 September 2013.

[111] His goals came in the sixth and tenth minutes of the first half, in a fixture which proved to be Valdez's last appearance for Al Jazira as he was ultimately sanctioned and fined for his celebration.

[113] Moments after the match, Valdez wrote in English via his Twitter account that his objective was never to offend anyone instead to make understand that he uses his balls when he is on the field and due to the bad luck in his last games he could not score goals, he expressed it in this manner.

He made his first appearance in the 2013–14 Greek Cup on 2 April 2014 in a semi-final 2–1 first-leg home victory against PAOK, playing the full 90 minutes of the fixture.

[132][133] Valdez made his 2014–15 Bundesliga debut in a 1–0 home victory against SC Freiburg on 23 August, playing until the 84th minute of the match before being substituted off of the field for Johannes Flum.

[141] Prior to the 2016 season, Primera División Paraguaya club Cerro Porteño announced their second attempt in the space of six months to sign Valdez.

Valdez admitted that he maintains contact with club president Juan José Zapag and that what remained for him in his career to achieve is to play in the Copa Libertadores, but he indicated that the transfer seemed difficult to occur.

[143] Colombian Categoría Primera A clubs Independiente Medellín and Atlético Nacional showed interest in the player and reports suggested that Valdez was to depart Seattle Sounders.

[153] Following Valdez' departure from Cerro Porteño, he was in conversations with Sol de America president and also turned down an offer from Guireña due to family reasons at the beginning of 2021.

Valdez was one of three players based outside of Paraguay, alongside Dante López at Israel's Maccabi Haifa and Víctor Hugo Mareco at Italian club Brescia.

[167] Valdez dutifully complied with his club's orders and subsequently missed out on the opportunity to claim a silver medal as Paraguay U23 finished in second place at the competition.

[171] Valdez would play 66 minutes of Paraguay's final group stage fixture against Trinidad and Tobago, which they won 2–0, as he was replaced by Nelson Cuevas.

During a friendly fixture several days prior to the Copa América, Valdez had scored his 11th national team goal in a 2–0 home victory against Romania on 11 June 2011.

Preceding a 2–0 defeat against Colombia in October 2012 which saw Paraguay bottom of the qualifiers table with only four points, Valdez responded in anger to Paraguayan fans that criticized the squad for their results: "I appreciate with my whole heart those few who continue to support us.

[190] In 2013, when new coach Victor Genes was appointed, Valdez was left out of Paraguay's team for a friendly against Germany and two World Cup qualifiers against Bolivia and Argentina.

[193] Valdez exited the field of play lifting his shirt to reveal for himself the mark that had been left from the player's studs and then applauding the crowd in appreciation for their attendance.

[206] In February 2014, it was reported that Valdez insisted on ways to financial help former national teammate Salvador Cabañas, who had suffered economic issues since being shot in the head in January 2010, and it was ultimately decided that Valdez would organize a charity match scheduled for June 2014 which would feature the likes of David Trezeguet[207] and Javier Saviola[208] in order to raise funds for Cabañas.

[212] On 29 and 30 January 2022, diverse Paraguayan newspapers reported that five people were arrested for attempting to kidnapp one of Haedo Valdez's family members in the area of San Joaquín in the Caaguazu Department.