Gynodioecy frequently results from the interplay of mitochondrial cytoplasmic male sterility (CMS) and nuclear fertility-restoration genes. Models suggest that maintaining cytonuclear gynodioecy requires that restorer genes incur a cost because otherwise they would increase toward fixation. Direct tests of costs of restorer alleles require knowledge of the underlying genetics of sex determination. We use a well characterized CMS system in Brassica napus in order to measure aspects of fitness in four lineages that vary in whether they carry the pol CMS gene or male-fertile cytoplasm (cam), and whether they carry the Rfp restorer of pol or Rfn restorer of the nap CMS gene. As expected, plants with pol CMS and only the Rfn restorer experienced reduced flower size, stamen length and pollen counts. Plants with pol and the Rfp restorer showed incomplete restoration with shorter stamens than both lines with cam cytoplasm and reduced pollen counts compared to plants with cam cytoplasm and the Rfp restorer. Among plants with cam cytoplasm, pollen counts were higher for those with the Rfp than Rfn restorer, indicating a greater cost of restoration associated with the Rfn. These results demonstrate that costs of restoration differ for the Rfn and Rfp alleles in B. napus.