Interbreeding between species (hybridization) typically produces unfit offspring. Reduced hybridization should therefore be favored by natural selection. However, this is difficult to accomplish because hybridization also sets the stage for genetic recombination to dissociate species-specific traits from the preferences for them. Here we show that this association is maintained by physical linkage (on the same chromosome) in two hybridizing Ficedula flycatchers. By analyzing the mating patterns of female hybrids and cross-fostered offspring, we demonstrate that species recognition is inherited on the Z chromosome, which is also the known location of species-specific male plumage traits and genes causing low hybrid fitness. Limited recombination on the Z chromosome maintains associations of Z-linked genes despite hybridization, suggesting that the sex chromosomes may be a hotspot for adaptive speciation.