While we don’t know for sure, we can guess by looking at organisms that exhibit both sexual and asexual behavior:
IMO (this is educated speculation, as this is somewhat outside my realm of expertise) sexual lifestyle of the baker’s yeast, Saccharomyces cerevisiae actually gives us hints into how sex might have evolved. Both this yeast and the divergent fission yeast (they diverged 1.1MYA) have two sexes that are determined by the sequence of DNA at the MAT locus in the genome. Baker’s yeast have two genes that can be copied (through gene conversion) at the locus, the MATa or MATα (alpha) genes. They are encoded on the left and right sides of the MAT locus. When a yeast is MATα, for example, the MATα gene will be at the MAT locus, the MATa gene will be transcriptionally silenced, and the transcription of the MATα gene at the MAT locus will make that yeast appear to other yeast as a MATα. It does this by secreting the alpha-peptide and presenting an A-receptor, so it both tells other yeast that it’s an α through the peptide, and is able to recognize other alphas through its receptor. This ensures that during sex the yeast will always mate with the opposite type.
The reason I bring this system up is obvious: it’s a very simple and elegant way of thinking about how sex could have evolved as it’s a way of getting two subtypes of species with very little evolutionary change. In essence, it’s the yeast’s way of mixing and matching advantageous evolutionary traits throughout the population. In a nutrient rich and healthy environment, baker’s yeast predominately (though 1% will still mate) exists as asexually propagating diploid (2 copies of each of their 16 chromosomes) cells. However, in stressful/nutrient poor conditions, yeast will mate and sporulate, and produce 4 spores, 2 MATa, 2 MATα, and each mixed and matched for 1 of the original 16 chromosomes. Once conditions get better, they mix and match further, and create a new heterogeneous population. Presumably, these mechanisms exist to ensure survival through the obvious advantage of variation in a population, more specifically through: (1) spread of rare genes that may confer fitness advantages in the new environmental condition, (2) the elimination of mutated genes that occur in asexually reproducing populations by genetic drift and mutation.
The thread has plenty of discussion on the topic if you’re interested.