Compte tenu des succès répétés enregistrés par la lutte de libération dans le domaine militaire et sur le plan diplomatique, il s’est révélé nécessaire de concrétiser cela à travers la création d’un gouvernement algérien. Pour cela, des efforts furent déployés et de larges consultations furent entamées au sein des frères arabes pour la formation d’un Gouvernement Provisoire de la République Algérienne en exil.
Avec l’arrivée de De Gaulle au pouvoir le 01 juin 1958, l’occasion fut propice pour une réponse à sa politique de la part du Comité de Coordination et d’Exécution qui a œuvré à la constitution de ce gouvernement.
Au cours du Congrès de Tanger tenu du 27 au 30 Avril 1958, le Front de Libération Nationale avait préparé le terrain avec la Tunisie et le Maroc à la proclamation de ce gouvernement qui aurait à assumer la responsabilité de la poursuite du combat pour le recouvrement de l’indépendance sur tous les plans.
A ce congrès étaient présents les partis officiels représentant les gouvernements du Maghreb arabe , à savoir le Maroc et la Tunisie ainsi que l’Algérie. Parmi les délégations des trois partis, il y avait le parti marocain al Istiqlal , la délégation du FLN et la délégation du parti du Néo-Destour tunisien. Les résolutions du congrès de Tanger aboutirent à la concrétisation de ce qu’espéraient les Algériens, à savoir la constitution d’un gouvernement provisoire algérien.
L’annonce officielle de la constitution du gouvernement a eu lieu au Caire le 19 septembre 1959 et à son tour, il annonça sa méthode de lutte dans un communiqué officiel lu sur les médias audiovisuels. Suite à cela, les reconnaissances internationales se sont succédées à partir du 19 septembre 1958 jusqu’au recouvrement de l’indépendance en 1962. Durant cette période, il y eut deux présidents pour trois gouvernements, à savoir Ferhat Abbès qui a présidé le premier gouvernement et Benyoucef Benkhedda qui a présidé à son tour les deux gouvernements suivants jusqu’au recouvrement de la souveraineté nationale le 5 juillet 1962.
Le mérite de la constitution du premier gouvernement provisoire algérien à l’extérieur revient au président égyptien Gamal Abdel Nasser et aux larges facilités accordées par son gouvernement à la délégation extérieure du Front de Libération Nationale.

Reconnaissances internationales

- 19 septembre 1958: Irak – Libye – Tunisie
- 20 septembre 1958: Royaume d'Arabie Séoudite – Corée du Nord
- 21 septembre 1958 : Egypte – Yemen
- 22 septembre 1958 : Chine populaire – Le Soudan
- 26 septembre 1958 : Le Vietnam
- 30 Septembre 1958 : La Guinée
- 15 décembre 1958 : La Mongolie
- 15 Janvier 1959 : Le Liban
- 12 Juin 1959 : La Yougoslavie
- 10 Juillet 1959: Le Ghana
- 20 Septembre 1959 : La Jordanie
- 07 Juin 1960 : Le Libéria