As opposed to the past where there was near total exclusion of women and their issues, women are now relatively speaking, increasingly engaged in state matters, and the public agenda is more open to including gender and women’s rights issues in some way. Basing this reflection on Uganda’s experience, this article explores the major strides made in terms of women’s engagement with the state and policy-making, which have largely made a mark on the basic legitimation battle or on theability to create a possibility for a gender-inclusive state arena. In the same vein, the reflective analysis presented in this article alerts us to the inherent pitfalls in the tokenistic shifting of the gender of the state, and the critical need for current ways of feminist interrogation and activism to move beyond basic legitimation to a more inventive and transformative posture in order to set redistributive struggles in motion again.