The mimetic butterflies Heliconius erato and Heliconius melpomene have undergone parallel radiations to form a near-identical patchwork of over 20 different wing-pattern races across the Neotropics. Previous molecular phylogenetic work on these radiations has suggested that similar but geographically disjunct color patterns arose multiple times independently in each species. The neutral markers used in these studies, however, can move freely across color pattern boundaries, and therefore might not represent the history of the adaptive traits as accurately as markers linked to color pattern genes. To assess the evolutionary histories across different loci, we compared relationships among races within H. erato and within H. melpomene using a series of unlinked genes, genes linked to color pattern loci, and optix, a gene recently shown to control red color-pattern variation. We found that although unlinked genes partition populations by geographic region, optix had a different history, structuring lineages by red color patterns and supporting a single origin of red-rayed patterns within each species. Genes closely linked (80-250 kb) to optix exhibited only weak associations with color pattern. This study empirically demonstrates the necessity of examining phenotype-determining genomic regions to understand the history of adaptive change in rapidly radiating lineages. With these refined relationships, we resolve a long-standing debate about the origins of the races within each species, supporting the hypothesis that the red-rayed Amazonian pattern evolved recently and expanded, causing disjunctions of more ancestral patterns.