The presence of incompatibility alleles in primary amphidiploids constitutes a reproductive barrier in newly synthesized wheat-rye hybrids. To overcome this barrier, the genome stabilization process includes large-scale chromosome rearrangements. In incompatible crosses resulting in fertile amphidiploids, the elimination of one of the incompatible alleles Eml-A1 or Eml-R1b can occur already in the somatic tissue of the wheat × rye hybrid embryo. We observed that the interaction of incompatible loci Eml-A1 of wheat and Eml-R1b of rye after overcoming embryo lethality leads to hybrid sterility in primary triticale. During subsequent seed reproductions (R1, R2 or R3) most of the chromosomes of A, B, D and R subgenomes undergo rearrangement or eliminations to increase the fertility of the amphidiploid by natural selection. Genotyping-by-sequencing (GBS) coverage analysis showed that improved fertility is associated with the elimination of entire and partial chromosomes carrying factors that either cause the disruption of plant development in hybrid plants or lead to the restoration of the euploid number of chromosomes (2n = 56) in the absence of one of the incompatible alleles. Highly fertile offspring obtained in compatible and incompatible crosses can be successfully adapted for the production of triticale pre-breeding stocks.