Several physical mechanisms have been proposed to explain allostery in proteins. They differ by the number of internal states that they assume a protein to occupy, leaving open the question of what controls the emergence of these distinct physical forms of allostery. Here, we analyze a simplified model of protein allostery under a range of physical and evolutionary constraints. We find that a continuum of mechanisms between two archetypes emerges through evolution. In one limit, a single-state mechanism exists where ligand binding induces a displacement along a single normal mode, and in the other limit, a multi-state mechanism exists where ligand binding induces a switch across an energy barrier to a different stable state. Importantly, whenever the two mechanisms are possible, the multi-state mechanism confers a stronger allosteric effect and thus a selective advantage. This work defines the essential constraints that distinguish single- and multi-state allostery and sets the stage for a physical theory of its evolutionary origins.