Legitimacy is a concept meant to capture the beliefs that bolster willing obedience. The authors model legitimacy as a sense of obligation or willingness to obey authorities (value-based legitimacy) that then translates into actual compliance with governmental regulations and laws (behavioral legitimacy). The focus is on the factors that elicit this sense of obligation and willingness to comply in a way that supports rational-legal authority. The framework posits that legitimacy has two antecedent conditions: trustworthiness of government and procedural justice. Using African survey data, the authors model the relationship between the existence of a relatively effective, fair, and trustworthy government and beliefs that government deserves deference to its rules. The authors find considerable evidence of a link between the extent of the trustworthiness of government and procedural justice and citizens’ willingness to defer to the police, courts, and tax department in a wide range of African societies.