L’annonce de la création du ouvernement provisoire algérien le 19 septembre 1958 au Caire a eu l’effet d’un choc psychologique qui a propulsé d’une manière foudroyante l’Algérie au-devant de la scène internationale. L’idée de la formation d’un gouvernement algérien a germé lors de la réunion des trois partis maghrébins au Maroc. Le 27 avril 1958, s’ouvrit, en effet, à Tanger une conférence des partis nationalistes du Maghreb, qui regroupait des délégués de l’Istiqlal marocain, du Destour tunisien et du FLN algérien. À l’ordre du jour de la conférence figurait en première position la question de «la Guerre de l’indépendance en Algérie». La conférence a non seulement proclamé unanimement le droit du peuple algérien à l’indépendance, mais elle a également voté une résolution finale, le 30 avril, formulée ainsi: «Considérant que le rassemblement du peuple algérien autour du FLN fait de celui-ci l’unique représentant de l’Algérie indépendante recommande la constitution, après consultation des gouvernements tunisien et marocain, d’un gouvernement algérien.»
L’annonce de cette création a été reportée à plusieurs reprises à cause des objections qui auraient été formulées aussi bien par le président tunisien Habib Bourguiba que par le roi marocain Mohammed V.