The overexpression of defined transcription factors in somatic cells results in their reprogramming into induced pluripotent stem (iPS) cells. The extremely low efficiency and slow kinetics of in vitro reprogramming suggest that further rare events are required to generate iPS cells. The nature and identity of these events, however, remain elusive. We noticed that the reprogramming potential of primary murine fibroblasts into iPS cells decreases after serial passaging and the concomitant onset of senescence. Consistent with the notion that loss of replicative potential provides a barrier for reprogramming, here we show that cells with low endogenous p19(Arf) (encoded by the Ink4a/Arf locus, also known as Cdkn2a locus) protein levels and immortal fibroblasts deficient in components of the Arf-Trp53 pathway yield iPS cell colonies with up to threefold faster kinetics and at a significantly higher efficiency than wild-type cells, endowing almost every somatic cell with the potential to form iPS cells. Notably, the acute genetic ablation of Trp53 (also known as p53) in cellular subpopulations that normally fail to reprogram rescues their ability to produce iPS cells. Our results show that the acquisition of immortality is a crucial and rate-limiting step towards the establishment of a pluripotent state in somatic cells and underscore the similarities between induced pluripotency and tumorigenesis.