Un autre cheval de bataille est celui de la guerre d'
Algérie, à laquelle ils s'opposent en raison de leur anticolonialisme. Le premier secrétaire général de l'histoire du PSU est Edouard Depreux. Ancien ministre de l'Intérieur SFIO de juin 1946 à novembre 1947, il s'est éloigné de son parti du fait de son aversion pour la politique algérienne de Guy Mollet (qu'explique son anticolonialisme) et de son opposition au projet de Communauté Européenne de Défense. En 1958, Edouard Depreux a voté contre l'investiture du
général de Gaulle et a fondé le parti socialiste autonome. Celui-ci fusionne avec l'union de la gauche socialiste, et une poignée de dissidents communistes issus du groupe Tribune du
Communisme créé en 1958 par Jean Poperen (qui est entré en lutte contre le
stalinisme après avoir vu la répression de l'insurrection hongroise de 1956). C'est l'acte de naissance de l'histoire du PSU, qui se veut le terreau idéologique de la gauche en tant parti politique français générateur et catalyseur de force de propositions.