Reprogramming of somatic cell nuclei to yield induced pluripotent stem (iPS) cells makes possible derivation of patient-specific stem cells for regenerative medicine. However, iPS cell generation is asynchronous and slow (2–3 weeks), the frequency is low (<0.1%), and DNA demethylation constitutes a bottleneck. To determine regulatory mechanisms involved in reprogramming, we generated interspecies heterokaryons (fused mouse embryonic stem (ES) cells and human fibroblasts) that induce reprogramming synchronously, frequently and fast. Here we show that reprogramming towards pluripotency in single heterokaryons is initiated without cell division or DNA replication, rapidly (1 day) and efficiently (70%). Short interfering RNA (siRNA)-mediated knockdown showed that activation-induced cytidine deaminase (AID, also known as AICDA) is required for promoter demethylation and induction of OCT4 (also known as POU5F1) and NANOG gene expression. AID protein bound silent methylated OCT4 and NANOG promoters in fibroblasts, but not active demethylated promoters in ES cells. These data provide new evidence that mammalian AID is required for active DNA demethylation and initiation of nuclear reprogramming towards pluripotency in human somatic cells.