How and when eukaryotes evolved remain major open questions. Also the phylogenetic relationships and the emergence order of major eukaryotic lineages remain unresolved, despite progress in phylogenomic analyses based on genome and transcriptome data across the eukaryotic tree. However, this information is biased towards multicellular taxa. Yet, environmental molecular analyses have uncovered a vast diversity of protists (broadly, microbial eukaryotes), many of which have uncertain phylogenetic position. Phylogenomics also suggests that endosymbiosis (e.g. mitochondrial acquisition) played a key role in eukaryotic evolution, shaping their genomes and leading to innovations. The first eukaryotes likely evolved in anoxic or transition-to-oxic (suboxic) environments, which may hold clues as to the occurring selective constraints, prior to colonizing new niches thanks to oxygen-respiring mitochondria. Despite so, little is known about the diversity and mode of evolution of eukaryotes in suboxic worlds, including microbial mats and stromatolites, where many inter-species interactions are likely to exist. I propose an integrative interdisciplinary approach to gain significant knowledge about early eukaryotic evolution according to the following hypotheses: i) High diversity suboxic environments, such as microbial mats, hide novel divergent protist lineages. ii) The study of natural fossilization processes of microbial eukaryotes in calcifying microbial mats such as stromatolites will lead to the definition of biosignatures in the past fossil record and to establish reference dates for the origin of eukaryotes and/or particular eukaryotic taxa. iii) Phylogenomic analysis of divergent protist lineages from suboxic environments will help resolving the eukaryotic tree of life and dating major splits in eukaryotic lineages. iv) Protist symbiosis with prokaryotes is widespread in suboxic worlds and that (endo)symbiotic-gene transfer has an important impact in protist evolution.