Reconstructing the histories of complex adaptations and identifying the evolutionary mechanisms underlying their origins are two of the primary goals of evolutionary biology. Taricha newts, which contain high concentrations of the deadly toxin tetrodotoxin (TTX) as an antipredator defense, have evolved resistance to self-intoxication, which is a complex adaptation requiring changes in six paralogs of the voltage-gated sodium channel (Na_v) gene family, the physiological target of TTX. Here, we reconstruct the origins of TTX self-resistance by sequencing the entire Na_v gene family in newts and related salamanders. We show that moderate TTX resistance evolved early in the salamander lineage in three of the six Na_v paralogs, preceding the proposed appearance of tetrodotoxic newts by ~100 million years. TTX-bearing newts possess additional unique substitutions across the entire Na_v gene family that provide physiological TTX resistance. These substitutions coincide with signatures of positive selection and relaxed purifying selection, as well as gene conversion events, that together likely facilitated their evolution. We also identify a novel exon duplication within Na_v1.4 encoding an expressed TTX-binding site. Two resistance-conferring changes within newts appear to have spread via nonallelic gene conversion: in one case, one codon was copied between paralogs, and in the second, multiple substitutions were homogenized between the duplicate exons of Na_v1.4. Our results demonstrate that gene conversion can accelerate the coordinated evolution of gene families in response to a common selection pressure.