La ville de Ciudad del Este est fondée en 1957. les hauts plateaux sont alors surtout peuplés de tribus amérindiennes. Les missionnaires sillonnent la région surtout depuis la fin du XIXe siècle, en particulier les missionnaires du Verbe-Divin, les salésiens et les rédemptoristes. Il y a un certain nombre de missionnaires allemands[1].
Par la constitution apostoliqueNulla nos Evangelii du 25 mars 1968 émise par le pape Paul VI, la prélature territoriale d'Encarnación et Alto Paraná est divisée en deux donnant naissance à la prélature territoriale d'Alto Paraná et à la prélature territoriale d'Encarnación (aujourd'hui diocèse d'Encarnación)[2].
La prélature territoriale d'Alto Paraná est élevée au rang de diocèse le par la constitution apostolique Magna quidem du pape Jean-Paul II[3]et prend son nom actuel le [1].
Un nouveau séminaire, le séminaire Saint-Joseph (de formation traditionnelle), est ouvert en 2004 formant des prêtres dans tout le pays en plus du séminaire national d'Asunción. Dès lors la majorité des prêtres du pays qui sont ordonnés tous les ans (plus d'une quinzaine) sort de ce séminaire.
Évêques
évêques d'Alto Paraná
Francisco Cedzich, S.V.D (11 mai 1968 - 23 décembre 1971)
Augustín Van Aaken, S.V.D (25 juillet 1972 - 19 avril 1990)