Genotyping by sequencing (GBS) is an efficient method of genotyping in numerous plant species. One of the crucial steps toward the application of GBS markers in crop improvement is anchoring them on particular chromosomes. In rye (Secale cereale L.), chromosomal localization of GBS markers has not yet been reported. In this paper, the application of GBS markers generated by the DArTseq platform for extending the high-density map of rye is presented. Additionally, their application is used for the localization of the Rfc1 gene that restores male fertility in plants with the C source of sterility-inducing cytoplasm. The total number of markers anchored on the current version of the map is 19,081, of which 18,132 were obtained from the DArTseq platform. Numerous markers co-segregated within the studied mapping population, so, finally, only 3397 unique positions were located on the map of all seven rye chromosomes. The total length of the map is 1593 cM and the average distance between markers is 0.47 cM. In spite of the resolution of the map being not very high, it should be a useful tool for further studies of the Secale cereale genome because of the presence on this map of numerous GBS markers anchored for the first time on rye chromosomes. The Rfc1 gene was located on high-density maps of the long arm of the 4R chromosome obtained for two mapping populations. Genetic maps were composed of DArT, DArTseq, and PCR-based markers. Consistent mapping results were obtained and DArTs tightly linked to the Rfc1 gene were successfully applied for the development of six new PCR-based markers useful in marker-assisted selection.