Novel adaptations must originate and function within an already established genome [ 1 ]. As a result, the ability of a species to adapt to new environmental challenges is predicted to be highly contingent on the evolutionary history of its lineage [ 2–6 ]. Despite a growing appreciation of the importance of historical contingency in the adaptive evolution of single proteins [ 7–11 ], we know surprisingly little about its role in shaping complex adaptations that require evolutionary change in multiple genes. One such adaptation, extreme resistance to tetrodotoxin (TTX), has arisen in several species of snakes through coevolutionary arms races with toxic amphibian prey, which select for TTX-resistant voltage-gated sodium channels (Nav) [ 12–16 ]. Here, we show that the relatively recent origins of extreme toxin resistance, which involve the skeletal muscle channel Nav1.4, were facilitated by ancient evolutionary changes in two other members of the same gene family. A substitution conferring TTX resistance to Nav1.7, a channel found in small peripheral neurons, arose in lizards ∼170 million years ago (mya) and was present in the common ancestor of all snakes. A second channel found in larger myelinated neurons, Nav1.6, subsequently evolved resistance in four different snake lineages beginning ∼38 mya. Extreme TTX resistance has evolved at least five times within the past 12 million years via changes in Nav1.4, but only within lineages that previously evolved resistant Nav1.6 and Nav1.7. Our results show that adaptive protein evolution may be contingent upon enabling substitutions elsewhere in the genome, in this case, in paralogs of the same gene family.