Twenty-five AFLPs, previously linked to fertility restoration genes for the male-sterilizing PAMPA cytoplasm (cms-P) in a restricted rye population, were studied in an enlarged population of 120 plants. A strong association with the trait was verified for 19 of the markers. The recombination of these markers was tested and two linkage groups were identified: one consisting of six and the other of eight AFLPs. The remaining markers were segregated as independent loci. Using wheat-rye addition and substitution lines, the AFLPs were assigned to individual rye chromosomes. AFLP profiles of such lines were generated to identify the DNA fragments co-migrating with individual markers. This identified 1R and 3R as the two chromosomes corresponding to the linkage groups of eight and six markers, respectively. Mapping in a DS2 x RXL10 population linked four additional AFLPs to chromosome arms 1RS, 3RL, 4RL and 6RL. RAPD and SSR markers mapped in various populations and known to be located on the appropriate chromosomes did not disrupt the C394-F2 population into sterile and fertile phenotypes. It was concluded that the identified markers would reduce by one half the number of primer pair combinations needed for molecular breeding programs or for the selection of parental forms for rye hybrid crosses.