"Evidence from microfossils strongly suggests that life arose on the earth long ago, probably within a few hundred million years of the planet's formation. Sedimentary rocks 3.5 billion years old (and perhaps those 3.8 billion years old) contain what appear to be fossil stromatolites, which are natural colonies formed by photosynthetic bacteria; within the stromalites one can see microscopic forms reminiscent of bacteria. If these presumed bacteria are direct ancestors of extant photosynthetic bacteria, life was already well developed by then, having passed through the stages that led to the most recent universal ancestor and the splitting of the ancestral lineage into the primary lines of descent.
"By comparing molecular sequences to infer genealogies, molecular phylogeneticists tell us that the two primary lines of descent lead to the eubacteria (or common bacteria, which include the photosynthetic bacteria) and to a second common lineage that subsequently divided to form the archaea (which like the eubacteria are prokaryotes) and the eukaryotes (which include all higher plants and animals). All these events appear to have preceded the oldest fossil stromatolites. So the eukaryotic lineage appears to be very ancient, about as ancient as the two prokaryotic lineages.
"The key unanswered question here concerns when on the eukaryotic line the eukaryotic type of cell formed. Eukaryotic cells seem structurally far more complex than their prokaryotic counterparts (from which they arose), so biologists generally believe that many evolutionary steps must have separated the two. Nevertheless, the eukaryotic stem on the phylogenetic tree of life spawns many branches before one gets to the split that separates the ancestors of plants from the ancestors of animals, which seems to have happened more than a billion years ago. There seem to have been many earlier branchings from the eukaryotic stem, all represented by unicellular eukaryotes (such as the slime molds, the flagellates, the trichomonads, the diplomonads, the microsporidia, among others).
"Clearly, eukaryotic history goes back far into the era when the earth's atmosphere contained little or no oxygen, well over two billion years ago. Our current concept of the origin of the eukaryotic cell is in flux, however, and an evolutionary sequence that appears simple when conceptualized on a phylogenetic tree diagram may be far more complex and interesting in reality. We know that the eukaryotic cell is of ancient origin, but we do not yet know the evolutionary dynamic that underlies its formation."
J. Peter Gogarten in the department of molecular and cell biology at the University of Connecticut at Storrs, gives a broader overview:
"The question is the subject of an ongoing and lively controversy. The best guesses for the time when eukaryotes evolved range from just below 2.0 billion years to around 3.5 billion years before the present.
"One of the less ambiguous sources of information is the fossil record. Work by Gonzalo Vidal of the University of Uppsala in Sweden indicates that single-celled planktonic eukaryotes certainly date back to 1.7 billion years B.P. and very likely to at least 2.2 billion years B.P. The early fossil record is very sparse, however, and small eukaryotic cells present in the fossil record would not necessarily have been positively identified. My colleagues generally agree that the fossil record provides only a most recent estimate for the time when eukaryotes were already abundant; they might have been around a long time before they made it into the fossil record in a recognizable form.
"Another approach is to date phylogenies by looking at a 'clock' of molecular changes that accumulate in the genetic code. Although that approach has been successfully used to decipher relations between organisms, calibrating it to measure the time elapsed since the divergence of phylogenetic branches is problematic; concerning the early evolution of life, there is no generally accepted approach. Most attempts to date early molecular phylogenetic trees used the emergence of eukaryotes (around 2.0 billion years B.P.) as a calibration point. Russell F. Doolittle and his co-workers at the University of California at San Diego recently attempted to extend the calibration further into the past, but this work is contested. The controversy centers on possible cases of horizontal gene transfer across phylogenetic branches that were ignored by these authors and on an insufficient correction for multiple substitutions. In addition, these backward extrapolations assume that the rate of molecular change at the time the eukaryotes originated is the same as it was during the metazoan evolution, when in fact it was probably much faster.
"The typical eukaryotic cell resulted from a symbiosis between different prokaryotic ancestors. Three prokaryotic components can be traced by comparing molecules in extant prokaryotes and eukaryotes. These components are the mitochondria (derived from purple bacteria), the plastids (from cyanobacteria), and the nucleocytoplasmic component (from archaebacteria). Other features in eukaryotic cells--for instance, the cytoskeleton--may also be of bacterial descent, but so far the molecular record has not yielded unambiguous clues as to their origin.
"The nucleocytoplasmic component of the eukaryotic cell branches off very early in the evolutionary radiation of the archaebacteria. There is an active dispute as to whether some of the archaebacteria are more closely related to the eukaryotic nucleocytoplasm than are others (proponents of the differing views are James Lake of the University of California at Los Angeles and Carl Woese of the University of Illinois at Urbana-Champaign). Regardless of how the debate is resolved, the ancestor of the eukaryotic nucleocytoplasm must have separated from the archaebacteria early in, or even before, the era when the major archaebacterial groups arose. In contrast, bacterial ancestors of mitochondria and plastids separated from the eubacteria lineage only after the evolutionary radiation that gave rise to the major eubacterial kingdoms. Therefore, it is likely that primitive eukaryotes lacking mitochondria and plastids were around a long time before they made it into the fossil record. I would be surprised if such eukaryotes did not date back to at least 3.0 billion years before the present.