Gynodioecy is the co-occurrence of females and hermaphrodites in populations. It is usually due to the combined action of cytoplasmic male sterility (CMS) genes and nuclear genes that restore male fertility. According to previous theoretical studies, it is very difficult to explain the maintenance of gynodioecy with CMS and male-fertile cytotypes, although it has been observed in some species. However, only very specific situations have been investigated so far. We present a model to investigate the conditions that promote the maintenance of this breeding system in the case of an outcrossed species when CMS and male-fertile (non-CMS) cytotypes are present in an infinite panmictic population. We show that the type of cost of restoration strongly affects the conditions for stable maintenance of gynodioecy. Stable nuclear-cytoplasmic gynodioecy requires a female advantage, which is a classical condition for gynodioecy, but also a cost of CMS for female fitness, which had been rarely investigated. A cost of restoration is also needed, which could affect either pollen or seeds. Finally, we found that gynodioecy was attainable for a large set of parameter values, including low differences in fitness among genotypes and phenotypes. Our theoretical predictions are compared with previous theoretical work and with results of empirical studies on various gynodioecious species.