Legitimacy is a key concept in political science. It has deep normative roots in democratic theory and refers usually to righteous, just, fair, and therefore acceptable rule. However, non-democracies also try to create a following among their citizens. They also engage in justifying their rule through politicization, be it of religion, ethnicity, or ideologies ranging from left-wing communism to right-wing nationalism. Against this backdrop, I pose the question: does it make sense to use the concept of legitimacy for both types of regimes, democracies and autocracies alike? Or, do we overstretch the concept when transplanting it to the non-democratic realm? And, empirically, how can we assess to what degree a non-democracy is viewed as legitimate by its citizens? I aim therefore at defining what legitimacy and legitimation is in autocratic settings; drawing a semantic map of rival concepts like support, trust, and loyalty; and tackling concrete challenges in measuring this elusive concept.