Most of the Precambrian (>538 Ma) fossil record, which includes the time before the onset of macroscopic multicellular life, consists of minute organically preserved remains of soft-bodied micro-organisms, i.e. non-pollen palynomorphs (NPP). These microfossils include single-celled prokaryotic or eukaryotic organisms, filamentous sheets and bacterial cellular aggregates, and occur in marine and lacustrine sediments through most of the Earth's history. Ancient NPP have informed our understanding of one of the biggest evolutionary steps in the history of life: the origin of the eukaryotic cell and the subsequent diversification of eukaryotic life before the evolution of macroscopic forms. The oldest widely accepted eukaryotic microfossils are large cells with opening structures and ornamentation from upper Paleoproterozoic units in China and India. NPP diversify through Meso- and Neoproterozoic Eras, notably recording the oldest multicellular life around 1 billion years ago. In the latest Neoproterozoic, during the advent of animal life, the NPP record allows us to study the cryptic evolution of animals while they were exclusively small and poorly or non-mineralized before the appearance of organisms with hard parts. We review the current understanding of the early eukaryotic evolution and major advances in Precambrian palaeontology through the lens of the NPP record in deep time.