Scholars have suggested that Indonesia's former president Suharto's New Order state legitimated itself by destroying the Partai Komunis Indonesia (Communist Party of Indonesia, PKI). In this article, the author points to the sexual politics underlying this process of legitimation that have been largely ignored in earlier analyses. She focuses 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 that eventually brought Suharto to power. It embodied a powerful, supportive logic by which Suharto's rule was sustained until mid-1998, creating a particular form of national, militarized identity. Another consequence of the sexual accusations Gerwani endured 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, but the remaining women's organizations were also 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 rather than emancipate women.