The “demos paradox” is the idea that the composition of a demos could never secure democratic legitimacy because the composition of a demos cannot itself be democratically decided. Those who view this problem as unsolvable argue that this insight allows them to adopt a critical perspective towards common ideas about who has legitimate standing to participate in democratic decision-making. We argue that the opposite is true and that endorsing the demos paradox actually undermines our ability to critically engage with common ideas about legitimate standing. We challenge the conception of legitimacy that lurks behind the demos paradox and argue that the real impossibility is to endorse democracy without also being committed to significant procedure-independent standards for the legitimate composition of the demos. We show that trying to solve the problem of the demos by appeal to some normative conception of democratic legitimacy is a worthwhile project that is not undermined by paradox.