We investigate multilocus patterns of differentiation between parental populations of two swallowtail butterfly species that differ at a number of ecologically important sex-linked traits. Using a new coalescent-based approach, we show that there is significant heterogeneity in estimated divergence times among five Z-linked markers, rejecting a purely allopatric speciation model. We infer that the Z chromosome is a mosaic of regions that differ in the extent of historical gene flow, potentially due to isolating barriers that prevent the introgression of species-specific traits that result in hybrid incompatibilities. Surprisingly, a candidate region for a strong barrier to introgression, Ldh, does not show a significantly deeper divergence time than other markers on the Z chromosome. Our approach can be used to test alternative models of speciation and can potentially assign chronological order to the appearance of factors contributing to reproductive isolation between species.