The Nordic countries are known for their well-functioning public administrations. In indices measuring control of corruption and the quality of the rule of law, they frequently occupy top positions. However, as we demonstrate in this article, a country's top position in comparative indices does not automatically imply that citizens view the state of affairs in the same way as depicted by experts. The observation is in no way trivial: Drawing on theories of procedural fairness, we go on to show—statistically, using individual level data—that widespread public perceptions about the unfairness of civil servants may have a negative effect on the legitimacy of the political system even in so-called high-trust and “least corrupt” settings such as the Nordic ones.