Being a quite small part of minute plants, cryptospores provide us with a very large window to look into the early greenery of the Earth. Although the last common ancestor of land plants may have evolved in the Proterozoic, plants with complex multicellular sporophytes ushered substantial diversification only from the Devonian. During the intervening time interval, cryptospores left key fossil record about the early land plant evolution. Here, we present a comprehensive overview of the cryptospore fossil record from the perspectives of morphology, taxonomy, biostratigraphy, biodiversity, paleogeography and biological affinity. Two different concepts of cryptospores, both sensu lato and sensu stricto, have been developed, especially in relation to whether this group involves the Cambrian sporomorphs in the algal-plant evolutionary transition. Based on over 200 studies spanning from the late early Cambrian through Middle Devonian (ca. 515 to 390 Ma), we evaluate the temporal diversity and spatial differentiation of cryptospores s.l. by quantitative means such as Chao2 estimator, non-metric multidimensional scaling and network analysis. The results underscore that 1) according to available fossil data, the Late Ordovician-early Silurian witnessed the initial expansion of early land plants in species diversity and distribution, with an increased potential for geographical differentiation; 2) as trilete spores emerged, geographical differentiation became more distinct among spore assemblages during the middle-late Silurian, but without further diversification of cryptospores; 3) palynofloras may still host diverse cryptospores in the Early Devonian, just before the demise of these spores; and 4) higher spatial, temporal and taxonomic resolution is required to fully decipher the spore-based early land plant evolution in the future. A newly compiled set of stratigraphic ranges of all cryptospore species shows necessity and prospect of recalibrating spore biozonation schemes with an increasing accumulation of fossil data. The nature of these microfossils recovers an evolving path from ancestral streptophyte algae to early embryophytes (eophytes), although the complete phylogenetic relationships of cryptospore-producing organisms remain to be elucidated. It is expecting to disclose some long-standing mysteries of plant terrestrialization with the research opportunities offered by cryptospores and the application of interdisciplinary approaches.