Human cancers display substantial intra-tumoral genetic heterogeneity, which facilitates tumor survival under changing microenvironmental conditions. Tumor substructure and its impact on disease progression and relapse are incompletely understood. In the current study, a high-throughput method that utilizes neutral somatic mutations accumulated in individual cells to reconstruct cell lineage trees was applied to hundreds of cells of human acute leukemia harvested from multiple patients at diagnosis and at relapse. The reconstructed cell lineage trees of acute myeloid leukemia (AML) patients demonstrated that leukemia cells at relapse were shallow (divide rarely) compared to cells at diagnosis and were closely related to their stem cell subpopulation, implying that in these instances relapse might have originated from rarely-dividing stem cells. In contrast, among acute lymphoid leukemia (ALL) patients, no differences in cell depth were observed between diagnosis and relapse. In one case of chronic myeloid leukemia (CML), at blast crisis, most of the cells at relapse were mismatch-repair deficient. In almost all leukemia cases, more than one lineage was observed at relapse, indicating that diverse mechanisms can promote relapse in the same patient. In conclusion, diverse relapse mechanisms can be observed by systematic reconstruction of cell lineage trees of leukemia patients.