L'annonce officielle de la constitution du GPRA 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, Ferhat Abbas, 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 Conseil national de la révolution algérienne (CNRA) lors de sa réunion tenue au Caire du 22 au 28 août 1958, au cours de laquelle le Comité de coordination et d'exécution (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 État 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.

Près d'un demi-siècle après l'indépendance, la célébration de la fête nationale fait encore débat. A la place du 5-juillet 1962, date de la proclamation officielle de cette indépendance, Abdelhamid Mehri, grande figure du FLN, propose celle du 19-septembre 1958 correspondant à la naissance du GPRA . Dans l'histoire nationale, le 5 juillet n'a, en réalité, jamais recueilli l'unanimité. L'indépendance a été acquise dans les faits le 19 mars, et confirmée par la voie d'un référendum populaire le 3 juillet 1962. Quant au 5-juillet, c'est une mauvaise étape de la colonisation. La date correspond à la prise d'Alger par les troupes du général de Bourmont débarquées une vingtaine de jours plus tôt, le 14 juin 1830, à Sidi Ferruch. La prise d'Alger a révélé les desseins de l'entreprise coloniale. Mal en point, la monarchie voulait faire main basse sur les trésors de la Régence afin de pouvoir corrompre les électeurs lors d'un scrutin majeur qui se préparait. Selon l'écrivain/enquêteur Pierre Péan, le trésor accaparé équivalait à 4,5 milliards d'euros. On imagine ce que pouvait représenter cette somme il y a près de deux siècles… Pour M. Abdelhamid Mehri, la restauration de l’Etat algérien, correspond bien à la naissance du GPRA, le 19 septembre 1958 Le Parlement, de son point de vue, est habilitée à trancher cette question de manière définitive. Le GPRA avait été reconnu par 35 Etats dans le monde et avait pu, en ce qui le concerne, signer des Traités internationaux pour le compte de l’Etat algérien que préfigurait la guerre d'indépendance.

Après l'arrivée au pouvoir du général de Gaulle et pour renforcer ses positions et sa légitimité politique, le FLN veut faire en sorte d'apparaître comme un ensemble cohérent, malgré les réelles dissensions internes, et acquérir davantage de poids que par son CCE (Comité de coordination et d'exécution). Il s'agit aussi d'attirer les reconnaissances officielles sur la scène internationale. Dans ce sens, la création d'un gouvernement provisoire semble être la meilleure voie. Le 19 septembre 1958, par une conférence de presse tenue au Caire, Ferhat Abbas, annonce la dissolution du CCE et la création du GPRA (Gouvernement provisoire de la république algérienne), tandis que Belkacem Krim l'annonce à Tunis. Ces deux conférences sont restituées dans ce sujet muet du Journal télévisé de 20 heures. L'Egypte et la Tunisie sont à la tête du soutien diplomatique et de l'aide matérielle à destination des nationalistes algériens. Le choix de l'appellation GPRA n'est pas sans rappeler, à dessein, le GPRF (Gouvernement provisoire de la République française) de la Libération. Le journal Le Monde parle d'ailleurs dans son édition du jour de « gouvernement algérien libre », rappelant inconsciemment la « France libre » de la Seconde Guerre mondiale.

Le gouvernement provisoire de la république algérienne comprend dix-huit membres dont les anciens du second CCE, à l'exception de Ouamrane, et s'installe à Garden-City dans la capitale égyptienne. L'organe de presse du FLN, El Moudjahid, annonce dans son édition du 20 septembre 1958 : « Parvenu à maturité, le FLN a pu donner naissance au gouvernement provisoire algérien. Celui-ci de par son origine et sa vocation répond bien à sa définition en tant que gouvernement. Il se situe au-dessus des nuances partisanes, exprime la souveraineté de tout le peuple, non l'opinion de telle ou telle fraction, et se place d'emblée au niveau de l'existence étatique internationale » (in Bernard Droz, Evelyne Lever, Histoire de la guerre d'Algérie 1954-1962, Paris, Le Seuil, collection « Points Histoire », 1982, p. 213)

La présidence du GPRA est confiée à Ferhat Abbas. Belkacem Krim, le seul des neuf historiques, devient vice-président avec en outre le titre de ministre des Forces armées. La composition établit un savant dosage entre politiques et militaires. Les dirigeants du FLN emprisonnés depuis l'interception de leur avion en octobre 1956 sont officiellement membres du GPRA.

D'emblée, quinze Etats africains et asiatiques le reconnaissent officiellement.

Le premier acte diplomatique du GPRA est de dénoncer dès le lendemain de sa création, à l'ONU, le référendum annoncé par le général De Gaulle.