Among the natural mechanisms used for wheat hybrid breeding, the most desirable is the system combining the cytoplasmic male sterility (cms) of the female parent with the fertility-restoring genes (Rf) of the male parent. The objective of this study was to identify Rf candidate genes in the wheat genome on the basis of transcriptome sequencing (RNA-seq) and paralog analysis data. Total RNA was isolated from the anthers of two fertility-restorer (Primépi and Patras) and two non-restorer (Astoria and Grana) varieties at the tetrad and late uninucleate microspore stages. Of 36,912 differentially expressed genes (DEGs), 21 encoding domains in known fertility-restoring proteins were selected. To enrich the pool of Rf candidates, 52 paralogs (PAGs) of the 21 selected DEGs were included in the analyses. The expression profiles of most of the DEGs and PAGs determined bioinformatically were as expected (i.e., they were overexpressed in at least one fertility-restorer variety). However, these results were only partially consistent with the quantitative real-time PCR data. The DEG and PAG promoters included cis-regulatory elements common among PPR-encoding genes. On the basis of the obtained results, we designated seven genes as Rf candidate genes, six of which were identified for the first time in this study.