We compare the historical demographies of two Müllerian comimetic butterfly species: Heliconius erato and Heliconius melpomene. These species show an extensive parallel geographic divergence in their aposematic wing phenotypes. Recent studies suggest that this coincident mosaic results from simultaneous demographic processes shaped by extrinsic forces over Pleistocene climate fluctuations. However, DNA sequence variation at two rapidly evolving unlinked nuclear loci, Mannose phosphate isomerase (Mpi) and Triose phosphate isomerase (Tpi), show that the comimetic species have quite different quaternary demographies. In H. erato, despite ongoing lineage sorting across the Andes, nuclear genealogical estimates showed little geographical structure, suggesting high historical gene flow. Coalescent-based demographic analysis revealed population growth since the Pliocene period. Although these patterns suggest vicariant population subdivision associated with the Andean orogeny, they are not consistent with hypotheses of Pleistocene population fragmentation facilitating allopatric wing phenotype radiation in H. erato. In contrast, nuclear genetic diversity, theta, in H. melpomene was reduced relative to its comimic and revealed three phylogeographical clades. The pattern of coalescent events within regional clades was most consistent with population growth in relatively isolated populations after a recent period of restricted population size. These different demographic histories suggest that the wing-pattern radiations were not coincident in the two species. Instead, larger effective population size (N(e)) in H. erato, together with profound population change in H. melpomene, supports an earlier hypothesis that H. erato diversified first as the model species of this remarkable mimetic association.