Gynodioecious species are defined by the co-occurrence of two clearly separated categories of plants: females and hermaphrodites. The hermaphroditic category may, however, not be homogeneous, as male fitness may vary among hermaphrodites as a result of many biological factors. In this study, we analysed estimates of pollen quantity and viability in the gynodioecious Beta vulgaris ssp. maritima, comparing hermaphrodites bearing a male-fertile cytotype and hermaphrodites bearing cytoplasmic male sterility (CMS) genes, which are counteracted by nuclear restoration factors. We show that: (i) pollen quantity continuously varies among restored hermaphrodites, suggesting a complex genetic determination of nuclear restoration; (ii) pollen viability was lower in restored (CMS) hermaphrodites than in non-CMS hermaphrodites, probably because of incomplete restoration in some of these plants; and (iii) pollen quantity and viability also varied among hermaphrodites with male-fertile cytotypes, possibly a result of a silent cost of restoration. Finally, we discuss the consequences of these results for pollen flow and the dynamics of gynodioecy.