Three types of sterile cytoplasm in cytoplasmic-male-sterility (CMS) maize, T, C and S, can be identified according to their fertility-restoration and mitochondrial DNA RFLP patterns. CMS-S, which is the least stable among the three types of CMS, is controlled by sterile cytoplasm interactions with certain nuclear-encoded factors. We constructed a high-resolution map of loci associated with male-restoration of CMS-S in BCl populations of maize. The map covers 1730.29 cM, including 32 RFLP, 51 SSR 62 RAPD and 21 AFLP markers. Genome-wide QTL analysis detected 6 QTLs with significant effects on male fertility as assessed by their starch-filled pollen ratios. Four QTLs out of six were located between the SSR markers MSbnlg1633-Mrasg20, MSbnlg1662-Msumc1126, MSumc1230-MSumc1525, and RAPD marker MraopQ07-2-MraopK06-2 on chromosome 2. Two other minor loci were mapped between MraopK16-1-Mraopi4-1, on chromosome 9, and between Msuncbnlg1139-MraopR10-2, on chromosome 6. The Rf3 nuclear restoring gene was precisely located on the chromosome 2, 2.29 cM to the left of umc1525 and 8.9 cM to the right of umc1230. The results provide important markers for marker-assisted selection of stable CMS-S maize.