In this paper I argue that ex-president Soeharto’s New Order state, which lasted from 1966 till 1998, legitimated itself not only by its destruction of the Communist Party of Indonesia (PKI, Partai Komunis Indonesia), as other scholars have suggested previously (Mortimer 1969 for example). I suggest that the sexual politics underlying this process of legitimation have so far been largely ignored. I focus on the military’s orchestrated campaign of slander and sexual innuendo against the PKI’s women’s organization Gerwani (Gerakan Wanita Indonesia, Indonesian Women’s Movement). This campaign was pursued for more than 30 years since the 1 October 1965 putsch in Indonesia which eventually brought Soeharto to power. It embodied a powerful supportive logic by which Soeharto’s rule was sustained until mid-1998, creating a particular form of national, militarized identity. Another consequence of the sexual accusations falsely hurled at Gerwani was the destruction of what was at the time one of the most powerful women’s movements in the world. Not only was Gerwani banned and destroyed, the remaining women’s organizations were brought under strict government control. The state even set up its own mass women’s organizations, under the umbrella of Dharma Wanita (Women’s Duty) which were intended to re-subordinate women, rather than to emancipate them. The feminist organizations in Indonesia which came up in the mid 1980s had to manoeuvre very carefully to avoid being called "Gerwani baru", "new Gerwani".