This article examines Frantz Fanon’s conception of a “new man” in the context of the psychological action campaign initiated by French military strategists during the Algerian war. Using archival research, the article draws parallels between military psychologists and Fanon’s search for a new man in a war of re-colonization for the former and decolonization for the latter. While the French military used sophisticated methods of brainwashing to bring about a new colonial subject, Fanon relied on anti-colonial political engagement, and an ambiguous relation to a rehabilitated European thought. The paper raises questions about Fanon’s dismissal of the long-term significance of brainwashing for individual agency, and the absence of an elaborate psychiatric response to counter the military psychological action campaign.