Social hierarchies are widespread in human and animal societies, and an individual’s position in its hierarchy affects both its access to resources and its fitness. Hierarchies are traditionally thought of in terms of variation in individual ability to win fights, but many are structured around arbitrary conventions like nepotistic inheritance rather than such traits as physical strength or weapon size. These convention-based societies are perplexing because position in the hierarchy appears to be gained irrespective of individual physical ability, yet social status strongly affects access to resources and fitness. It remains unclear why individuals abide by seemingly arbitrary conventions regarding social status when they stand to benefit by ignoring these conventions and competing for top positions or access to resources. Using data from wild spotted hyenas collected over 27 y and five generations, we show that individuals who repeatedly form coalitions with their top allies are likely to improve their position in the hierarchy, suggesting that social alliances facilitate revolutionary social change. Using lifetime reproductive success as a fitness measure, we go on to demonstrate that these status changes can have major fitness consequences. Finally, we show that the consequences of these changes may become even more dramatic over multiple generations, as small differences in social rank become amplified over time. This work represents a first step in reconciling the advantages of high status with the appearance of “arbitrary” conventions that structure inequality in animal and human societies.