Sexual reproduction is a trait shared by all complex life, but the complete account of its origin is missing. Virtually all theoretical work on the evolution of sex has been centered around the benefits of reciprocal recombination among nuclear genes, paying little attention to the evolutionary dynamics of the multi-copy mitochondrial genome. Here we develop a mathematical model to study the evolution of nuclear alleles inducing cell fusion in an ancestral population of clonal proto-eukaryotes. Segregational drift maintains high mitochondrial variance between clonally reproducing hosts, but the effect of segregation is opposed by cytoplasmic mixing which tends to reduce variation between cells in favor of higher heterogeneity within the cell. Despite the reduced long-term population fitness, alleles responsible for sexual cell fusion can spread to fixation. The evolution of sex requires negative epistatic interactions between mitochondrial mutations and is promoted by strong purifying selection, low mutant load and weak mitochondrial-nuclear associations. We argue that similar conditions were maintained during the late stages of eukaryogenesis, facilitating the evolution of sexual cell fusion and meiotic recombination without compromising the stability of the emerging complex cell.