A classic problem in the literature on authority is that those with the power to enforce cooperation and proper norms of conduct can also abuse or misuse their power. The present research tested the argument that concerns about legitimacy can help regulate the use of power to punish by invoking a sense of what is morally right or socially proper for power-holders. We tested this idea in a laboratory experiment using public goods games in which one person in each group was selected to be a “designated punisher” who could give out material punishment that was either costly or costless to the punisher. Results show that costly punishment is perceived as more legitimate (proper) than costless punishment and that designated punishers engaged in more proper (“prosocial”) punishment and less abusive (“antisocial”) punishment when punishment was costly. These results highlight the importance of legitimacy in both motivating and regulating the enforcement of cooperation.