Single-cell technologies are offering unparalleled insight into complex biology, revealing the behavior of rare cell populations that are masked in bulk population analyses. One current limitation of single-cell approaches is that lineage relationships are typically lost as a result of cell processing. We recently established a method, CellTagging, permitting the parallel capture of lineage information and cell identity via a combinatorial cell indexing approach. CellTagging integrates with high-throughput single-cell RNA sequencing, where sequential rounds of cell labeling enable the construction of multi-level lineage trees. Here, we provide a detailed protocol to (i) generate complex plasmid and lentivirus CellTag libraries for labeling of cells; (ii) sequentially CellTag cells over the course of a biological process; (iii) profile single-cell transcriptomes via high-throughput droplet-based platforms; and (iv) generate a CellTag expression matrix, followed by clone calling and lineage reconstruction. This lentiviral-labeling approach can be deployed in any organism or in vitro culture system that is amenable to viral transduction to simultaneously profile lineage and identity at single-cell resolution.