In vivo lineage tracing holds great potential to reveal fundamental principles of tissue development and homeostasis. However, lineage tracing in humans relies on DNA mutations that are extremely rare. In mice, the improved genetic labeling approach has low resolution over cell division histories. Here, we demonstrated for the first time that frequent epimutations on DNA methylation can be exploited to infer lineage histories in normal cells, enabled by our newly developed computational method MethyTree. Using both in-house and public sparse single-cell DNA methylation datasets with known lineage labels, MethyTree reconstructed lineage histories at high resolution and accuracy across different cell types, stages, and species. Applying MethyTree, we identified the first fate decision in human embryo development and pinpointed in total ~230 clones of hematopoietic stem cells in mice. Our study opens the door for high-resolution, noninvasive lineage tracing in mice, humans and beyond. Overall design: In this study, we carried out an in vitro lineage tracing experiment using blood progenitors extracted from a single adult mouse and generated single-cell multi-omic readouts. Specifically, we extracted Lin−cKit+Sca1- blood progenitors from a single mouse, introduced LARRY lineage barcodes in these cells by lentiviral infection, cultured them in vitro for 6 days in a media that supports cell expansion and pan-myeloid differentiation, and finally profiled these cells with a modified Camellia-seq protocol that we developed recently to obtain LARRY lineage barcode, transcriptome, and DNA methylome simultaneously in single cells. This table only contains data on the DNA methylome of single cells.