The predominance of sex as a mode of reproduction in multicellular organisms presents a paradox because the reproductive rate of individuals within a sexual population, producing 50% males, is, in theory, only one half that of asexual individuals. Sexual forms, when they arose, should thus have been rapidly eliminated through competition from asexual conspecifics, and sex, therefore, should not exist. The basis of this paradox is the hypothesis that the competitive abilities of sexual individuals could not evolve rapidly enough to overcome this `cost of males' before the elimination of the sexual trait by its asexual competitors. A modified form of this hypothesis was not supported when tested experimentally using laboratory populations of the red flour beetle (Tribolium castaneum). The results instead show that rapid evolution can enable a sexual population to eliminate a non-evolving competitor, even when that competitor has a reproductive advantage that substantially exceeds that arising from the two-fold cost of male production.