Against Nigeria they were sent on their way when Celso Ayala scored the quickest goal of the tournament.
Against Slovenia they spent most of the match a goal and a man down, but got there in the end thanks to the late, late show of super-sub Nelson Cuevas.
In 1998 they went on in the second round to give enormous problems to one of the powers of the European game, taking France to within six minutes of a penalty shoot-out.
Can they really perform as well against the Germans?
It is asking a great deal.
Paraguay are an ageing side and between the win on Wednesday and the showdown on Saturday there was little time for them to rest.
Their efforts against Slovenia will have taken a lot out of them - even the youngsters are suffering.
Roque Santa Cruz seemed short of fitness against the Slovenes. It was his worst performance of the group games.
The same is also true of Paraguay's other potent attacking arm, Francisco Arce.
He is the supplier, and Santa Cruz the finisher.
The fact that both were below par on Wedneday makes the comeback against Slovenia all the more remarkable.
But now the Germans represent a far more demanding physical challenge.
Even without the suspended Carsten Ramleow, Dietmar Hamann and Christian Ziege they would seem to be strong enough to steam-roll the Paraguayans.
Cesare Maldini's men will need the pace of Jorge Campos on the break, and the willingness of their strikers to fight for scraps up front.
Most of all, though, they must recapture their defensive solidity.
As long as they can keep the Germans at bay, they have the firepower to sneak a goal - especially if Cuevas produces more heroics.