The South American team went into their final Group B game knowing that they needed to win by two clear goals and hope that Spain defeated South Africa.
I'm proud of this team and I think we can accomplish a lot more
Jose Luis Chilavert
But at half-time it seemed as though their World Cup campaign was over.
Carlos Paredes had been sent off after 21 minutes and Milenko Acimovic had scored for Slovenia.
However, Paraguay - inspired by susbstitutes Nelson Cuevas and Jorge Campos - scored three times in the last 25 minutes to transform the match.
With Spain beating South Africa 3-2, Paraguay now face Germany in the second round.
"We played much of the match a man down, but our team stayed together," said Chilavert.
"I'm proud of this team and I think we can accomplish a lot more.
"We're a small country, but we have lots of quality players. We played against a difficult opponent, but we played with pride."
Chilvert also thanked the Spanish team for defeating South Africa.
"Many thanks to Fernando Hierro and the rest of the Spanish team for beating South Africa and helping us move on to the next round," said Chilavert.
"I hope Paraguay will be able to repay them some day and that they go to the final.
Paraguay coach Cesare Maldini said that watching his team from the sidelines was stressful.
"You have to suffer in football," said the 70-year-old. "Our team suffered a lot."
"We had to fight a lot in this match, but our team is fit. We fought and achieved a good result and a good match."
Paraguay had thrown away a two-goal lead in their opening game against South Africa and then lost to Spain.
But Maldini said he was always confident his team would win a place in the last 16.
"In the first matches we were not so lucky.
"We had a bad result in our first game against South Africa but when I came to this match I was hopeful of qualifying."
And Maldini is looking forward to his team's second-round match.
"Like all World Cup games it will be very difficult," he said.
"Now we will relax a little bit. We have time to think before the next match and we have to play as we know how to play."