La tâche la plus urgente concerne l'Algérie. De Gaulle multiplie les voyages (le premier a lieu dès le 3 juin 1958), et s'achemine vers la solution de l'indépendance : il propose l'autodétermination aux Algériens en 1959.

Le référendum du 8 janvier 1961 sur le principe de l'autodétermination apporte au chef de l'État un soutien massif, puisqu'il recueille 75% de "oui". Mais les négociations sont difficiles à mener, compliquées par les partisans de l'Algérie française, par l'intransigeance du FLN et par le putsch des généraux français, le 22 avril 1961, qui échoue en quelques jours.

Après les pourparlers officieux menés par Georges Pompidou et des représentants du FLN, les négociations s'ouvrent sous la conduite de Louis Joxe, ministre des Affaires algériennes. Elles aboutissent aux accords d'Évian, signés le 22 mars 1962, acceptés par référendum en France le 8 avril, et en Algérie le 1er juillet. L'Algérie peut accéder à l'indépendance, mais une volonté de coopération a été maintenue entre les deux États.

Dans le même temps, le chef de l'Etat entend respecter la parole de la France concernant la signature des traités de Rome de 1957. Pour que la France entre dans la Communauté économique européenne dès le 1er janvier 1959, une réforme financière est mise en place par Antoine Pinay (le nouveau franc est lancé à cette date) ; les barrières douanières tombent offrant les produits français à la concurrence européenne. La France est poussée à la modernisation.