Historical inferences from genetic data increasingly depend on assumptions about the genealogical process that shapes the frequencies of alleles over time. Yet little is known about the structure of human genealogies over long periods of time and how they depart from expectations of standard demographic models, such as that attributed to Wright and Fisher. To obtain such information and to examine the recent evolutionary history of mtDNA and Y-chromosome haplotypes in the Icelandic gene pool, we traced the matrilineal and patrilineal ancestry of all 131,060 Icelanders born after 1972 back to two cohorts of ancestors, one born between 1848 and 1892 and the other between 1798 and 1742. This populationwide coalescent analysis of Icelandic genealogies revealed highly positively skewed distributions of descendants to ancestors, with the vast majority of potential ancestors contributing one or no descendants and a minority of ancestors contributing large numbers of descendants. The expansion and loss of matrilines and patrilines has caused considerable fluctuation in the frequencies of mtDNA and Y-chromosome haplotypes, despite a rapid population expansion in Iceland during the past 300 years. Contrary to a widespread assumption, the rate of evolution caused by this lineage-sorting process was markedly faster in matrilines (mtDNA) than in patrilines (Y chromosomes). The primary cause is a 10% shorter matrilineal generation interval. Variance in the number of offspring produced within each generation was not an important differentiating factor. We observed an intergenerational correlation in offspring number and in the length of generation intervals in the matrilineal and patrilineal genealogies, which was stronger in matrilines and thus contributes to their faster evolutionary rate. These findings may have implications for coalescent date estimates based on mtDNA and Y chromosomes.