It is broadly accepted that changes in gene regulation are a key driver of phenotypic differences between closely related species, and play an important role in short-term adaptations. However, the specific regulatory changes that occurred during the recent evolution of humans are largely unknown. To this end, we have produced and analyzed dozens of DNA methylation maps from chimpanzees and humans, including both modern and archaic human groups. We found ~1,400 differentially methylated regions that emerged on our lineage after the split from Neanderthals and Denisovans. Functional analyses of these genes revealed that our vocal tract has gone through a particularly rapid evolution that is not shared by other archaic human groups. Additionally, we detected substantial regulatory changes in the NFIX gene, and show that this gene might have been a major driver of changes in our craniofacial and vocal features. We also show that changes in isoform ratio of the AUTS2 gene, which are unique to anatomically modern humans, might have played a key role in our cognitive abilities, and in our susceptibility to Autism. Altogether, this study establishes a comprehensive catalogue of regulatory changes in recent human history.