Assigning single cell transcriptomes to cellular lineage trees by lineage tracing has transformed our understanding of differentiation during development, regeneration, and disease. However, lineage tracing is technically demanding, often restricted in time-resolution, and most scRNA-seq datasets are devoid of lineage information. Here we introduce Gene Expression Memory-based Lineage Inference (GEMLI), a computational tool allowing to robustly identify small to medium-sized cell lineages solely from scRNA-seq datasets. GEMLI allows to study heritable gene expression, to discriminate symmetric and asymmetric cell fate decisions and to reconstruct individual multicellular structures from pooled scRNA-seq datasets. In human breast cancer biopsies, GEMLI reveals previously unknown gene expression changes at the onset of cancer invasiveness. The universal applicability of GEMLI allows studying the role of small cell lineages in a wide range of physiological and pathological contexts, notably in vivo. GEMLI is available as an R package on GitHub (https://github.com/UPSUTER/GEMLI).