Nacque a Encarnación, figlio di un emigrato tedesco, Hugo Strößner di Hof, Baviera, e di Heriberta Matiauda. Stroessner, veterano della Guerra del Chaco, salì nei ranghi militari fino a diventare generale nel 1952. Il colpo di Stato compiuto dal movimento del 4 maggio 1954, che elevò alla presidenza della repubblica Tomás Romero Pereira, sostituendolo a Federico Chávez, spianò la strada a Stroessner che prese il potere il 15 agosto del 1954, abolendo la costituzione. Fu candidato unico alla presidenza in diverse elezioni, e il supporto degli Stati Uniti gli permise di restare in carica per decenni. Stroessner represse con durezza qualsiasi movimento di opposizione, ma si guadagnò il favore degli strati più poveri della popolazione grazie a un sistema di assistenza pubblica più avanzato che in altri paesi dell'America del Sud.
Alla fine, tuttavia, il suo rifiuto di indire elezioni democratiche e la dissoluzione dell'Unione Sovietica decretarono la fine degli aiuti statunitensi al regime. Il Partido Colorado, al quale Stroessner apparteneva, iniziò a esercitare critiche e opposizione nei suoi confronti, fino a deporlo nel 1989, per mano di un altro membro del partito, il generale Andrés Rodríguez. Tale formazione politica è successivamente rimasta al potere ininterrottamente per 19 anni, vincendo le elezioni anche in regime democratico. La successione di presidenti appartenenti al partito Colorado si è interrotta con la vittoria della coalizione di sinistra, capeggiata da Fernando Lugo, nelle elezioni del 20 aprile 2008.
La città orientale di Puerto Flor de Lis venne ribattezzata Puerto Presidente Stroessner in suo onore, ma nel 1989 il nome fu cambiato nuovamente in Ciudad del Este. Stroessner visse in esilio a Brasilia, capitale del Brasile, fin dal giorno in cui venne rovesciato e, nel 1997, fu condannato in contumacia per crimini contro l'umanità. La sua, dopo quella di Fidel Castro, è stata la dittatura più duratura (35 anni) nell'America Latina. Alfredo Stroessner Matiauda fu ricoverato nell'ospedale Santa Luzia a Brasilia il 29 luglio 2006, e morì il 16 agosto dello stesso anno, a 93 anni.