In cycling tissues, adult stem cells may be lost and subsequently replaced to ensure homeostasis. To examine the frequency of stem cell replacement, we analyzed the population dynamics of labeled stem cells in steady-state mouse spermatogenesis. Our results show that spermatogenic stem cells are continuously replaced, on average within 2 weeks. The analysis exposes a simple and robust scaling behavior of clone size distributions that shows stem cell replacement to be stochastic, meaning that stem cells are equipotent and equally likely to be lost or to multiply to replace their neighbors, irrespective of their clonal history. The surprisingly fast rate of stem cell replacement is supported experimentally by 3D clone morphology and by live-imaging of spermatogonial migration. These results suggest that short-lived stem cells may be a common feature of mammalian stem cell systems and reveal a natural mechanism for matching the rates of cell proliferation and loss in tissue.