Every animal grows from a single fertilized egg into an intricate network of cell types and organ systems. This process is captured in a lineage tree: a diagram of every cell’s ancestry back to the founding zygote. Biologists have long sought to trace this cell lineage tree in individual organisms and have developed a variety of technologies to map the progeny of specific cells. However, there are billions to trillions of cells in complex organisms, and conventional approaches can only map a limited number of clonal populations per experiment. A new generation of tools that use molecular recording methods integrated with single cell profiling technologies may provide a solution. Here, we summarize recent breakthroughs in these technologies, outline experimental and computational challenges, and discuss biological questions that can be addressed using single cell dynamic lineage tracing.