A legutóbbi világbajnokságot követően Anibal Ruíz személyében új szövetségi kapitány érkezett a válogatott élére. Akkoriban úgy tűnt, az együttes megérett egy alapos generációváltásra, azonban az új mesternek végül "csak" két meghatározó futballistáról kellett lemondania - Celso Ayala és José Luis Chilavert pótlása így sem ígérkezett könnyűnek.
A selejtezősorozat első mérkőzésén a kapuban Ricardo Tavarelli állt, a mezőnyben pedig a középhátvéd Carlos Gamarra vette a kezébe a karmesteri pálcát. Peruban éppen utóbbi szerzett vezetést a piros-fehér-kékeknek, azonban Claudio Pizarróék erre négy góllal válaszoltak. Talán nem meglepő, hogy a következő mérkőzéseken Tavarelli helyét Justo Villar foglalta el, és az évekig Chila árnyékában a kispadon kuporgott hálóőr ezután csak egy meccsen kapott szerepet (bár az éppen a Brazília elleni otthoni mérkőzés volt).
Az első körben elszenvedett vereséget zsinórban három győzelem követte, amely nagyban köszönhető a Roque Santa Cruz, José Saturnino Cardozo támadókettősnek. A fiatal csillag és az öreg harcos kiváló párost alkotott abban az időszakban, így négy forduló után Paraguay kilenc ponttal a selejtezőcsoport élén találta magát, megelőzve az eggyel lemaradt Argentínát és Brazíliát. A következő mérkőzésen éppen utóbbival csapott össze a gárda Asunciónban, és a fordulatos, sok helyzetet hozott mérkőzésen végül mindkét együttes elégedett lehetett a 0-0-s döntetlennel.
A bolíviai túrára így egy önbizalommal telt paraguayi válogatott utazott el, ám La Pazban Gamarráék meglepő vereséget szenvedtek. Az utolsó fél órában emberhátrányban futballoztak a hazaiak, mégis sikerült begyötörniük a győztes gólt. Buenos Airesben azonban már jobban teljesített a védelem, a Monumental stadion közönsége rezignáltan vehette tudomásul, hogy Justo Villar kapus kivédte a Carlos Tévez, Javier Saviola, Hernán Crespo támadótrojka szemét, és még azután is képes volt megőrizni hálóját a góltól, hogy a 61. percben Angel Ortíz a kiállítás sorsára jutott.
2004 nyarán némi intermezzo következett, egészen pontosan Athénba volt hivatalos az olimpiai válogatott, ahol túlkorosként Carlos Gamarra játszotta a főszerepet. A középhátvéd irányításával a csapat egészen a döntőig menetelt, a megszerzett ezüst a dél-amerikai ország első olimpiai érme volt. Visszatérve hazájába a csapatkapitány ott folytatta, ahol Görögországban abbahagyta, az ő góljával győzte le otthon a csapat a meglepően masszív Venezuelát.
A kilencedik és a tizedik játéknapon aggodalomra adhatott okot a piros-fehér-kékek szurkolóinak, hogy sérülés miatt sem Gamarra, sem Santa Cruz nem léphetett pályára, a gárda nélkülük két 1-1-es döntetlent ért el, előbb Kolumbia ellen idegenben, majd Peru ellen otthon remiztek Cardozóék. Ezzel, a selejtezősorozat féltávját elhagyva Paraguay 16 ponttal a harmadik helyen állt a két favorit, Argentína és Brazília mögött, az üldözőboly azonban meglehetősen közel helyezkedett el, három 13 pontos válogatott képében.
Éppen ezért jött rosszul a következő két idegenbeli mérkőzés, melyekről pont nélkül volt kénytelen hazatérni az együttes. Előbb Montevideóban a két veterán középhátvéd, Gamarra és Paolo Montero csatája végződött utóbbi győzelmével (az 1-0-ra elveszített találkozón a mindent eldöntő gólt Montero fejelte), majd Ecuadorból tért haza a csapat egy súlyos, 5-2-es zakóval.
Utóbbi vereség után a paraguayi közvélemény elsősorban Cardozót kezdte ki, a veterán csatár pedig a következő, Chile elleni hazai találkozón igyekezett visszanyerni a drukkerek kegyeit, mégpedig sikerrel, hiszen a 2-1-re megnyert meccsen ő szerezte a vendéglátók második gólját (ez volt a hetedik találata a sorozatban, amivel a támadó házi gólkirályi címét is bebiztosította). A győzelemmel az az Anibal Ruíz is fellélegezhetett, akinek egy nem megfelelő eredmény bizonyosan az állásába került volna.
A 14. fordulóban Porto Alegrébe vezetett a paraguayiak útja, ahol a lehengerlően futballozó brazilok ellen nem volt esélye a gárdának a pontszerzésre - a 4-1-re végződött találkozó érdekességét az jelentette, hogy a végeredményt Robinho állította be, akinek tétmeccsen ez volt az első gólja a selecaóban. Következett két hazai mérkőzés, előbb Bolíviát szórták meg a pampák győzelmi kényszertől hajtott harcosai (4-1 lett annak a találkozónak a vége), majd a már továbbjutott Argentína is vereséggel tért haza Asunciónból.
A vendégek szövetségi kapitánya, Marcelo Bielsa kísérletezésre használta fel a 90 percet, ám mégsem ez, hanem Gabriel Heinze pocsék játéka döntötte el a három pont sorsát: a Manchester United hátvédjének bakija kellett ahhoz, hogy Roque Santa Cruz megszerezze a vezetést a hazaiaknak, majd az 56. percben a balbekk begyűjtötte második sárga lapját is, reménytelen helyzetbe hozva együttesét.
Két mérkőzéssel a vége előtt Gamarráéknak mindössze két pontra volt szükségük ahhoz, hogy bebiztosítsák a németországi világbajnokságra való kijutást, a sorsolás szeszélye pedig éppen egy verhető ellenfelet, Venezuelát sodorta az útjukba. Maracaibóban pedig a vendégek nem is hagyták kihasználatlanul az adódó lehetőséget, Nelson Haedo-Valdez góljával 1-0-s győzelmet arattak, amivel kvalifikálták magukat a nagy seregszemlére.
Az utolsó, kolumbiai kiruccanásnak ilyenformán semmi jelentősége nem volt, elvégre Paraguayban nem igazán foglalkoztak azzal, hogy a nemzeti válogatott a harmadik vagy a negyedik helyezettként kvalifikálja magát a vébére. Az 1-0-s hazai győzelemnek azonban a kolumbiaiak sem örülhettek igazán, hiszen az ötödik, pótselejtezőt érő helyre végül Uruguay futott be. Így 28 ponttal, rosszabb egymás elleni eredménnyel a negyedik helyen zárta selejtezőbeli szereplését Paraguay válogatottja, az ugyancsak 28 pontos Ecuador, és a két szuperfavorit, Brazília és Argentína mögött.