Cellular barcoding is a technique in which individual cells are labeled with unique nucleic acid sequences, termed barcodes, so that they can be tracked through space and time. Cellular barcoding can be used to track millions of cells in parallel, and thus is an efficient approach for investigating heterogeneous populations of cells. Over the past 25 years, cellular barcoding has been used for fate mapping, lineage tracing and high-throughput screening, and has led to important insights into developmental biology and gene function. Driven by plummeting sequencing costs and the power of synthetic biology, barcoding is now expanding beyond traditional applications and into diverse fields such as neuroanatomy and the recording of cellular activity. In this review, we discuss the fundamental principles of cellular barcoding, including the underlying mathematics, and its applications in both new and established fields.