François Mitterrand
Đệ ngũ cộng hoà và đối lập với Gaulle > Cuộc "vượt sa mạc"

Năm 1958, Mitterrand là một trong số ít ứng cử viên để Charles de Gaulle chỉ định làm lãnh đạo chính phủ, và cho kế hoạch của de Gaulle về một nền Đệ ngũ Cộng hoà. Ông đã thay đổi sự đối lập của mình trong hoàn cảnh de Gaulle quay trở lại: cuộc khủng hoảng tháng 5 năm 1958 và áp lực quân đội. Tháng 9 năm 1958, quyết định đối đầu với Charles de Gaulle, Mitterrand đưa ra một lời kêu gọi bỏ phiếu "phản đối" trong cuộc trưng cầu dân ý về hiến pháp, tuy nhiên nó vẫn được thông qua ngày 4 tháng 10 năm 1958. Liên minh thất bại gồm PCF và một số nhà chính trị cộng hoà cánh tả (như Mendès-France và Mitterrand).
Thái độ này có thể là một yếu tố khiến Mitterrand mất ghế trong cuộc bầu cử lập pháp năm 1958, bắt đầu một chiến dịch "vượt sa mạc" lâu dài (thuật ngữ này thường được áp dụng cho sự suy tàn ảnh hưởng của de Gaulle trong một giai đoạn tương tự). Quả thực, ở vòng hai cuộc bầu cử lập pháp, Mitterrand được những người Cộng sản ủng hộ tuy nhiên Nhóm Công nhân Quốc tế Pháp (SFIO) từ chối rút lui ứng cử viên của họ. Sự chia rẽ này khiến ứng cử viên phe phe de Gaulle được bầu. Một năm sau, ông trúng cử làm đại diện cho Nièvre trong Thượng viện, nơi ông là một phần của Nhóm Dân chủ cánh Tả. Cùng lúc ấy, ông không được chấp nhận vào bộ máy của Đảng Xã hội Thống nhất (Parti socialiste unifié, PSU) do Mendès-France, cựu đối thủ bên trong của Molletvà là cựu thành viên có tư tưởng cải cách của Đảng Cộng sản, lập ra. Các lãnh đạo PSU đưa ra quyết định của mình dựa trên việc ông không từ chức khỏi nội các của Mollet và quá khứ Vichy của ông.
Cũng trong năm ây, trên Đại lộ de l'Observatoire ở Paris, Mitterrand tuyên bố đã thoát khỏi những viên đạn ám sát bằng cách nấp phía sau một hàng rào, Vụ Observatory. Vụ việc khiến ông trở nên rất nổi tiếng, lần đầu khuyến khích những tham vọng chính trị của ông. Một số người chỉ trích ông tuyên bố rằng chính ông dựng lên vụ ám sát, dẫn tới một phản ứng dữ dội chống Mitterrand. Sau này ông nói rằng trước đó ông đã được đại biểu cánh hữu Pesquet cảnh báo rằng ông đang là mục tiêu của một đơn vị ám sát Algérie française và buộc tội Thủ tướng Michel Debré là người đứng sau. Trước khi biến mất, Pesquet tuyên bố rằng Mitterrand đã lập ra một nỗ lực giả về cuộc đời ông. Một vụ khởi tố đã được thực hiện chống lại Mitterrand nhưng sau đó nó đã bị huỷ bỏ.
Trong cuộc bầu cử năm 1962, ông giành lại ghế trong Quốc hội với sự ủng hộ của PCF và SFIO. Hoạt động trong cánh tả thống nhất ở Nièvre, ông ủng hộ việc tập hợp các lực lượng cánh tả ở mức độ quốc gia, gồm cả PCF, nhằm thách thức sự thống trị của phái de Gaulle. Hai năm sau, ông trở thành chủ tịch của Đại hội đồng Nièvre. Tuy những người đối lập với De Gaulle tự tổ chức thành các câu lạc bộ, ông thành lập nhóm riêng của mình, Hội nghị các định chế cộng hoà (Convention des institutions républicaines hay CIR). Ông tăng cường vị thế của mình như một người đối lập cánh tả với Charles de Gaulle bằng cách xuất bản Le Coup d'État permanent (Cuộc đảo chính thường trực, 1964), chỉ trích quyền lực cá nhân của de Gaulle, sự suy yếu của nghị viện và chính phủ, việc tổng thống có quyền tối cao với các công việc ngoại giao và quốc phòng, vân vân.