„Nelson Antonio Haedo Valdez egyike a legtehetségesebb paraguayi futballistáknak, s 2006-ban éppen második hazájában, Németországban mutatathatja meg tudását a nagyvilágnak, hiszen a Bayern Roque Santa Cruzával alkothat támadó duót a világbajnokságon” – vezettük fel 2006-os vb-életrajzát.

Neslon afféle csodagyerekként már 15 évesen a felnőttek között futballozott odahaza az Atlético Tembetary együttesében, s 2001-ben igazolt Németországba, a Werder Bremen amatőrcsapatába. A serdülőcsapatban eltöltött pár napot próbajátékon, majd „vizsgamérkőzésén” négyszer is eredményes tudott lenni. Két év alatt olyannyira alkalmazkodott a német labdarúgásához, hogy egyrészt bekerült hazája válogatottjának keretébe a FIFA ifjúsági világbajnokságán (négy U20-as fellépésén egyszer volt eredményes), másrészt a DFB maga is megpendítette előtte, hogy akár német állampolgárságot is szerezhetne. Két év alatt 18 gólt lőtt a B-csapatban (ahol társa volt többek között a magyar Nánási Krisztián is), és 2002-ben már a felnőttek között is bemutatkozhatott: az Energie Cottbus elleni bajnokin léphetett pályára a 82. percben Christian Schulz helyén. Amatőrstátuszból elő is léptették gyorsan profivá az akkor 19 éves reménységet, s egészen 2007-ig szóló szerződést kötöttek vele. Klaus Allofs sportigazgató gyakran mondogatta akkoriban, hogy máris a jövő egyik reményeként-zálogaként emlegetik a fiatal dél-amerikait Brémában, maga az egykori kiváló, sokszoros német válogatott csatár a Regionalliga (területi bajnokság) legnagyobb csillagának nevezte Valdezt.

Valdez a 2003-2004-es, bajnoki aranyat és kupagyőzelmet termő esztendőben szerzett nevet magának a Bundesligában, hiszen ebben a csodálatos esztendőben kapta a „szupercsere” titulust, legelőször a Schalkénak pár másodperccel beállása után betalálva. Amikor végre a kezdőbe jelölte őt Thomas Schaaf a Hannover ellen, a csatár duplázni tudott és egy gólpasszt is kiosztott. A kupában a Lübeck ellen finálét érő gólt szerzett a hosszabbításban, a bajnokságban pedig a Hertha és a HSV elleni mérkőzéseken is bemutathatta szaltós gólörömét.

Nyáron a felnőtt válogatottal részt vehetett a Copa Américán, ahol háromszor húzhatta magára a piros-fehér mezt, s rendszeresen tagja volt a vb-selejtezőket vívó gárdának, ahol Roque Santa Cruz sérülése idején nagyon komolyan számoltak vele. Brémában Aílton távozása után Klose miatt került távol a kezdőtől, Klasnic is sokkal hasznosabban futballozott nála, de Haedo a 2004-05-ös Bundesliga-idényben így is hétszer volt eredményes, pedig térdszalag-szakadása miatt jó pár hetet ki is kellett hagynia. Viszont a BL-ben a Valencia elleni idegenbeli mérkőzésen tíz perccel a vége előtt csereként beállva két gólt is szerzett, ami miatt ki is tört egy kellemetes kis verekedés a gyepen az „őrült spanyolok” baráti kezdeményezésére.

Ruiz szövetségi kapitány magától értetődően magával vitte a mindössze négy selejtezőn pályára lépő Valdezt a németországi világbajnokságra.

Már előtte leigazolta a Dortmund 4.7 millió euróért, de a tornán nem volt eredményes. A klubcsapatában sem tudta beváltani a hozzá fűzött reményeket, lévén egyetlen idényben sem lőtt tíz bajnoki gólnál többet.