Trioecy, the co-existence of females, males and hermaphrodites, is a rare sexual system in plants that may be an intermediate state in transitions between hermaphroditism and dioecy. Previous models have identified pollen limitation as a necessary condition for the evolution of trioecy from hermaphroditism. In these models, the seed-production and pollen production of females and males relative to those of hermaphrodites, respectively, are compromised by self-fertilization by hermaphrodites under pollen- limitation. Here, we investigate the evolution of trioecy via the invasion of cytoplasmic male sterility (CMS) into androdioecious populations in which hermaphrodites co-occur with males and where the male determiner is linked to a (partial) fertility restorer. We show that the presence of males in a population renders invasion by CMS more difficult. However, the presence of males also facilitates the maintenance of trioecy even in the absence of pollen limitation by negative frequency-dependent selection, because males reduce the transmission of CMS by females by siring sons (which cannot transmit CMS). We discuss our results in light of empirical observations of trioecy in plants and its potential role in the evolution of dioecy.