1959-1962 : les débuts de la Ve République
La tâche la plus urgente concerne l'Algérie. De Gaulle multiplie les voyages et s'achemine vers la solution de l'indépendance : en 1959, il propose l'autodétermination aux Algériens et organise en 1961 un référendum sur ce thème : 75% des Français disent " oui " à l'autodétermination de l'Algérie. C'est un soutien massif pour le chef de l'Etat et un revers pour le partisans de l'Algérie française qui multiplient les attentats et tentent même un putsch à Alger en avril 1961. Les négociations entre Français et Algériens finissent par aboutir aux accords d'Evian, signés le 22 mars 1962, acceptés par référendum en France et en Algérie. L'Algérie peut accéder à l'indépendance, mais une volonté de coopération a été maintenue entre les deux Etats.

Si les séquelles de la guerre d'Algérie persistent dans les années qui suivent (rapatriement des Français et des Harkis, attentats de l'OAS), le chef de l'État est toutefois libéré du problème algérien et peut désormais s'attacher à renforcer le rang de la France.