Many traits evolve in parallel in widely separated populations. The evolutionary radiation of threespine sticklebacks provides a powerful model for testing the molecular basis of parallel evolution in vertebrates. Although marine sticklebacks are completely covered with bony armor plates, most freshwater populations have dramatic reductions in plates. Recent genetic studies have shown that major changes in armor patterning are likely due to regulatory alterations in the gene encoding the secreted signaling molecule ectodysplasin (EDA). In mammals, mutations in many different components of the EDA-signaling pathway produce similar changes in hair, teeth, sweat glands, and dermal bones. To test whether other genes in the EDA pathway also control natural variation in armor plates, we identified and mapped stickleback EDA Receptor (EDAR), the EDAR-Associated Death Domain adaptor, Tumor Necrosis Factor Receptor (TNFR) SuperFamily member 19, its adaptor TNFR-Associated Factor 6, and the downstream regulator nuclear factor kappa B Essential Modulator (NEMO). In contrast to the diversity of genes underlying ectodermal dysplasia disease phenotypes in humans, none of these EDA pathway components map to chromosomes previously shown to modify armor plates in natural populations, though EDAR showed a small but significant effect on plate number. We further investigated whether these genes exhibit differences in copy number, target size, or genomic organization that might make them less suitable targets for evolutionary change. In comparison with EDA, all these genes have smaller surrounding noncoding (putative regulatory) regions, with fewer evolutionarily conserved regions. We suggest that the presence of highly modular cis-acting control sequences may be a key factor influencing the likelihood that particular genes will serve as the basis of major phenotypic changes in nature.