The history of human population size is important to understanding human evolution. Various studies 1- 5 have found evidence for a founder event (bottleneck) in East Asian and European populations associated with the human dispersal out-of-Africa event around 60 thousand years ago (kya) before present. However, these studies have to assume simplified demographic models with few parameters and do not precisely date the start and stop times of the bottleneck. Here, with fewer assumptions on population size changes, we present a more detailed history of human population sizes between approximately ten thousand to a million years ago, using the pairwise sequentially Markovian coalescent (PSMC) model applied to the complete diploid genome sequences of a Chinese male (YH) 6 , a Korean male (SJK) 7 , three European individuals (Venter 8 , NA12891 and NA12878 9 ) and two Yoruba males (NA18507 10 and NA19239). We infer that European and Chinese populations had very similar population size histories before 10–20kya. Both populations experienced a severe bottleneck between 10–60kya while African populations experienced a milder bottleneck from which they recovered earlier. All three populations have an elevated effective population size between 60–250kya, possibly due to a population structure 11 . We also infer that the differentiation of genetically modern humans may have started as early as 100–120kya 12 , but considerable genetic exchanges may still have occurred until 20–40kya.