Papoulias je bio ministar vanjskih poslova u okviru više uzastopnih vlada PASOK-a, a najviše se pamti po normalizaciji odnosa između Grčke i Albanije krajem 1980-tih godina. Vladajuća partija je 1995. također ispregovarala "privremeni sporazum" između Atine i Skoplja.
Ardışık PASOK hükümetlerinde dışişleri bakanı olarak görev yapmış olan Papulyas, en çok 1980'lerin sonunda Yunanistan ile Arnavutluk arasındaki ilişkileri normale döndürmesiyle hatırlanıyor. 1995 yılında, iktidar partisi Atina ile Üsküp arasındaki "geçici anlaşmayı" da müzakere etmişti.