Gender quotas are increasingly being adopted not just by democracies, but also autocracies. Yet in autocracies, while gender quotas may still empower women, they may also grant dictators domestic and international legitimacy for having adopted the quota. Does this trade-off shape public attitudes toward quotas in autocracies? Are citizens living in autocratic regimes less supportive of gender quotas knowing they may legitimize the dictator? Or do the potential benefits of empowering women outweigh these costs? In this paper, we answer these questions by exploring this trade-off directly through a survey experiment in Algeria. The survey was fielded during the 2019-2020 Hirak protests, a mass uprising that toppled long-time dictator Abdelaziz Bouteflika and then continued against the remnants of his regime. In this context of mass frustration with the regime, we hypothesize that the potential costs of legitimizing the regime will outweigh the benefits of empowering women, leading Algerians to negatively evaluate gender quotas when presented with the trade-off. We conduct a survey experiment in which respondents are primed to think of how gender quotas empower women, how they might legitimize dictators, or both, forcing them to evaluate the trade-off. When primed about the gains to women, Algerians tended to become significantly more supportive of gender quotas than in the control. However, when primed about the legitimacy they may grant to the regime, Algerians were no more supportive than the control. Finally, when presented explicitly with the trade-off, the costs tended to outweigh the gains to women, and Algerians were likewise no more supportive than in the control. This finding is supported by cross-national analyses of eleven Arab countries using the Arab Barometer data.