Gender quotas are used to elect most of the world’s legislatures. Still, critics contend that quotas are undemocratic, eroding institutional legitimacy. We examine whether quotas diminish citizens’ faith in political institutions. Conducting survey experiments in twelve democracies with 17,000 respondents, we compare the legitimacy-conferring effects of both quota-elected and non-quota-elected local legislative councils relative to all-male councils. We find that women confer legitimacy to political decisions and decision-making processes, including when elected through quotas. Though we observe a quota penalty, wherein citizens prefer gender balance attained without a quota relative to gender balance attained with one, this penalty is often small (and sometimes non-significant), especially in countries with higher-threshold quotas. Quota debates are thus better framed around the most relevant counterfactual: the comparison is not between women’s descriptive representation with and without quotas, but between men’s political dominance and women’s inclusion.