MOTIVATION: Recent imaging technologies allow for high-throughput tracking of cells as they migrate, divide, express fluorescent markers and change their morphology. The interpretation of these data requires unbiased, efficient statistical methods that model the dynamics of cell phenotypes. RESULTS: We introduce treeHFM, a probabilistic model which generalizes the theory of hidden Markov models to tree structured data. While accounting for the entire genealogy of a cell, treeHFM categorizes cells according to their primary phenotypic features. It models all relevant events in a cell's life, including cell division, and thereby enables the analysis of event order and cell fate heterogeneity. Simulations show higher accuracy in predicting correct state labels when modeling the more complex, tree-shaped dependency of samples over standard HMM modeling. Applying treeHFM to time lapse images of hematopoietic progenitor cell differentiation, we demonstrate that progenitor cells undergo a well-ordered sequence of differentiation events. AVAILABILITY AND IMPLEMENTATION: The treeHFM is implemented in C++. We provide wrapper functions for the programming languages R (CRAN package, https://CRAN.R-project.org/package=treeHFM) and Matlab (available at Mathworks Central, http://se.mathworks.com/matlabcentral/fileexchange/57575-treehfml). SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.