Hematopoietic stem cells (HSCs) are the source for the life-long supply of functional cells in peripheral blood while they simultaneously maintain their own reserve pool. However, there is accumulating evidence that HSCs are themselves subject to quantitative and qualitative exhaustion. Although several processes linked to mitotic activity can potentially account for the observed aging phenomena (e.g., DNA damage, telomere shortening, epigenetic modification), a precise understanding of HSC exhaustion is still missing. It is particularly unclear how individual aging processes on the single-cell level translate on the phenotypic level of the overall tissue and whether there is a functional implication of an age-structured HSC population. We address these issues by applying a novel mathematical model of HSC organization in which division-specific, cumulative alterations of stem cell quality determine the phenotypic and functional appearance of the overall cell population. Adapting the model to a number of basic experimental findings, we quantify the level of additional heterogeneity that is introduced by a population of individually aging cells. Based on this model, we are able to conclude that division-dependent processes of cellular aging explain a wide range of phenomena on HSC exhaustion and that HSC aging needs to be considered as a highly heterogeneous process. We furthermore report that functional heterogeneity between young and old HSCs appears closely similar to the phenomena described for long- and short-term repopulating cells. We speculate whether differential, division-coupled stem cell aging introduces an intra-animal variability that also accounts for heterogeneity with respect to the repopulation ability of HSCs.