Compte tenu de la nouvelle situation induite par la guerre de libération à savoir
- les nombreux succès enregistrés depuis son déclenchement aussi bien sur le plan interne qu'externe;
- la réussite des attaques du 20 août 1955;
- les nouvelles organisations issues du Congrès de la Soummam et l'unification de la direction nationale à travers le Conseil National de la Révolution Algérienne (CNRA) et le Comité de Coordination et d'Exécution;
- l'intensification de l'activité diplomatique et l'obtention du soutien de la majorité des pays arabes et de pays amis à travers le monde;
- l'impact de la Révolution Algérienne sur la politique interne de la France et la chute des gouvernements successifs;
Il devenait nécessaire pour les dirigeants de la Révolution au sein du CCE d'annoncer la constitution du gouvernement provisoire de la république algérienne, notamment pour parer à l'amplification des manœuvres françaises à l'encontre de la question algérienne et des allégations de la France concernant l'inexistence de représentant légitime pour engager des négociations.

L'annonce officielle de la constitution du gouvernement provisoire de la République Algérienne eut lieu au Caire le 19 septembre 1958. Le même jour, fut rendue publique la première déclaration du Président du GPRA, définissant les circonstances de la naissance de celui-ci et les objectifs visés par sa création. Ce gouvernement est intervenu en exécution des décisions prises par le CNRA lors de sa réunion tenue au Caire du 22 au 28 août 1958, au cours de laquelle le CCE fut chargé d'annoncer la création d'un gouvernement provisoire, pour parachever la mise en place des institutions de la Révolution et la reconstruction d'un Etat algérien moderne.
Le Gouvernement Provisoire avait mis les autorités françaises devant le fait accompli alors que celles-ci prétendaient ne pas avoir d'interlocuteur pour négocier.
Entre 1958 et 1962, il y eut trois formations du gouvernement provisoire de la République Algérienne.

1ère formation : 1958 - 1960

Mr Ferhat ABBES Président
Mr Krim BELKACEM Vice-Président, Ministre des forces armées
Mr Ahmed BEN BELLA Vice-Président
Mr Hocine AIT AHMED Vice-Président
Mr Rabah BITAT Vice-Président
Mr Mohamed BOUDIAF Ministre d'Etat
Mr Mohamed KHIDER Ministre d'Etat
Mr Mohamed Lamine DEBAGHINE Ministre des Affaires Etrangères
Mr Mahmoud CHERIF Ministre de l'armement et de l'approvisionnement
Mr Lakhdar BENTOBBAL Ministre de l'Intérieur
Mr Abdelhafid BOUSSOUF Ministre des Liaisons Générales et des Communications
Mr Abdelhamid MEHRI Ministre des Affaires Nord Africaines
Mr Ahmed FRANCIS Ministre des Affaires économiques et financières
Mr Mhamed YAZID Ministre de l'Information
Mr Benyoucef BENKHEDDA Ministre des Affaires Sociales
Mr Ahmed Tewfik EL MADANI Ministre des Affaires Culturelles
Mr Lamine KHENE Secrétaire d'Etat
Mr Omar OUSSEDIK Secrétaire d'Etat
Mr Mustapha STAMBOULI

2ème formation : 1960 - 1961

Mr Ferhat ABBES Président
Mr Krim BELKACEM Vice-Président, Ministre des Affaires Etrangères
Mr Ahmed BEN BELLA Vice-Président
Mr Hocine AIT AHMED Vice-Président
Mr Rabah BITAT Vice-Président
Mr Mohamed BOUDIAF Ministre d'Etat
Mr Mohamed KHIDER Ministre d'Etat
Mr Saïd MOHAMMEDI Ministre d'Etat
Mr Abdelhamid MEHRI Ministre Affaires Sociales et Culturelles
Mr Abdelhafid BOUSSOUF Ministre de l'Armement et des Liaisons Générales
Mr Ahmed FRANCIS Ministre des Finances et des Affaires économiques
Mr Mhamed YAZID Ministre de l'Information
Mr Lakhdar BENTOBBAL Ministre de l'Intérieur

3ème formation : 1961 - 1962

Mr Benyoucef BENKHEDDA Président & Ministre des Finances et des Affaires économiques
Mr Krim BELKACEM Vice-Président, Ministre de l'Intérieur des Affaires Etrangères
Mr Ahmed BEN BELLA Vice-Président
Mr Mohamed BOUDIAF Vice-Président
Mr Hocine AIT AHMED Ministre d'Etat
Mr Rabah BITAT Ministre d'Etat
Mr Mohamed KHIDER Ministre d'Etat
Mr Lakhdar BENTOBBAL Ministre d'Etat
Mr Saïd MOHAMMEDI Ministre d'Etat
Mr Saad DAHLAB Ministre des Affaires Etrangères
Mr Abdelhafid BOUSSOUF Ministre de l'Armement et des Liaisons Générales
Mr Mhamed YAZID Ministre de l'Information

Le 19 septembre 1958 fut annoncé (proclamé) le gouvernement provisoire de la République Algérienne…..
Cette proclamation faite au nom d'un peuple en lutte depuis quatre ans pour son indépendance a ressuscité l'Etat Algérien absorbé(englouti) par l'occupation militaire en 1832 et gommé de manière cruelle et injuste de la carte politique d'Afrique du Nord.
Ainsi s'achève la pire opération de violation intervenue au cours du siècle dernier visant à dépouiller un peuple de sa nationalité, détourner le cours de son histoire , le priver de tous ses moyens vitaux, et l'atomiser en individualités.
Ainsi s'achève également la longue nuit, la nuit des mythes et légendes et s'achève enfin l'époque du mépris, de l'humiliation et de l’asservissement.
Voilà quatre années que ce peuple est sur le champ de bataille, résistant devant l'une des forces militaires les plus puissantes au monde et que sont tombés au champ de l'honneur et de la dignité plus de six cent mille de ses enfants dont le sang a arrosé la longue route glorieuse de la liberté . La France a jeté ce peuple aux tyrans colonialistes et les chefs militaires excellent chaque jour dans sa torture et son assassinat. Cependant, malgré ses souffrances et malgré les milliers de victimes, il est demeuré ferme dans sa conviction, convaincu que l'heure de la liberté arrivera sans aucun doute…..
L'Armée de Libération Nationale, avec ses moyens limités, combat – et la victoire est à ses côtés – une armée française dotée des armes les plus modernes d'artillerie, d'aviation et de la marine.
Le GPRA renouvelle le serment de demeurer éternellement fidèle aux valeurs suprêmes pour lesquelles des sacrifices ont été consentis : la liberté , la justice et la libération sociale….
Le GPRA, issu de la volonté du peuple, est conscient, dans ce domaine, de toutes ses responsabilités qu'il assumera entièrement, le premier de ses devoirs étant de guider le peuple et l'armée jusqu'à l'avènement de la libération nationale….
Le peuple algérien est un peuple pacifique ; il n'a pris les armes que contraint par les colonialistes et après avoir épuisé tous les recours pacifiques pour recouvrer sa liberté et son indépendance, le mythe de l'Algérie française et la fable de l'assimilation n'étant que le produit politique de la force et de la violence .
L'Algérie n'est pas la France et le peuple algérien n'est pas français et la tentative de franciser l'Algérie est une opération stérile et un crime condamné par la charte des Nations Unies…
L'Algérie combattante adresse ses remerciements à tous les Etats réunis au Congrès de Bandoeng de même qu'elle les assure de sa gratitude pour leur aide matérielle et leur soutien moral…
Le GPRA, quant à lui, est disposé à négocier ….Le GPRA a enregistré avec une immense satisfaction la reconnaissance de certains états auxquels il adresse ses remerciements et il y a d'autres états dont il attend la reconnaissance prochainement…
A la fin de cette déclaration, nous tenons à rappeler que la poursuite de la guerre continue une menace permanente pour la paix dans le monde et appelons aussi bien les individus que les gouvernements à conjuguer leurs efforts pour mettre un terme à cette guerre qui constitue une tentative néocolonialiste…
Nous espérons vivement que cet appel soit entendu.