Quand, à la Toussaint 1954, commença l'insurrection algérienne contre l'oppression coloniale imposée par l'impérialisme français, le gouvernement de Paris était dirigé par Mendès-France. Mitterrand était son ministre de l'Intérieur. La réaction de ce gouvernement fut la même que celle de son prédécesseur face aux révoltes des peuples colonisés : il se lança dans la répression avec l'envoi de bataillons de parachutistes, de quinze compagnies de CRS et de gardes mobiles. De 60 000 hommes en Algérie en 1954, on passa à 500 000 à la fin 1956.

Le MTLD, le principal parti nationaliste, fut interdit. Par centaines, ses militants furent arrêtés. Dans les commissariats, les passages à tabac devinrent la routine, ce que pudiquement on appelait « les interrogatoires poussés ».

L'écrivain François Mauriac dans un article intitulé La Question dénonça les mauvais traitements et les actes de torture commis sur des détenus algériens. Mitterrand, le ministre de l'Intérieur d'alors en réponse rendit hommage à la police française, Mendès-France l'appuya en déclarant : « Il n'y aura de la part du gouvernement ni hésitation, ni atermoiement, ni demi-mesure... il n'y aura aucun ménagement contre la sédition ».

En janvier 1956 une nouvelle majorité dite de gauche, le Front Républicain, fut élue sur un programme de « recherche de la paix et de la concertation en Algérie ». Guy Mollet, dirigeant du Parti Socialiste, forma le gouvernement, appelant une fois de plus Mitterrand au ministère de la Justice, Chaban-Delmas au ministère des Anciens combattants, et nomma Mendès-France ministre d'Etat. Afin d'avoir les mains libres en Algérie, Guy Mollet se fit voter les « pleins pouvoirs » par sa majorité de Front Républicain, pouvoirs spéciaux qui furent votés par les députés du PCF. Le 7 janvier 1957, il remit tous les pouvoirs de police dans le département d'Alger au général Massu commandant la 10e division parachutiste afin de « liquider le terrorisme urbain ».

Ce qu'on allait appeler « la bataille d'Alger » commençait. Elle fut menée à coups de rafles massives et aveugles. Les interpellés furent systématiquement soumis à la torture et souvent exécutés ensuite. Dans un rapport à ses supérieurs hiérarchiques, le secrétaire général de la Préfecture de police d'Alger signalait que, sur 24 000 personnes pour lesquelles il avait signé une assignation à résidence, 3 024 avaient disparu! De plus il précisait que ce chiffre était sans doute inférieur à la réalité, les militaires n'ayant pas toujours le temps de faire cette « demande » pour chaque personne arrêtée.

Les ministres de gauche de l'époque savaient tout cela. Ils en étaient même les mieux et les premiers informés. Pour le moins ils laissèrent faire, ils couvrirent, et fournirent aux tortionnaires tous les moyens matériels et humains dont ils purent avoir besoin. Quant aux quelques journalistes qui dénonçaient ces faits, ils furent souvent poursuivis en justice et les rares journaux qui les publiaient fréquemment saisis.