Genes responsible for human-specific phenotypes may have been under altered selective pressures in human evolution and thus exhibit changes in substitution rate and pattern at the protein sequence level. Using comparative analysis of human, chimpanzee, and mouse protein sequences, we identified two genes (PRM2 and FOXP2) with significantly enhanced evolutionary rates in the hominid lineage. PRM2 is a histone-like protein essential to spermatogenesis and was previously reported to be a likely target of sexual selection in humans and chimpanzees. FOXP2 is a transcription factor involved in speech and language development. Human FOXP2 experienced a >60-fold increase in substitution rate and incorporated two fixed amino acid changes in a broadly defined transcription suppression domain. A survey of a diverse group of placental mammals reveals the uniqueness of the human FOXP2 sequence and a population genetic analysis indicates possible adaptive selection behind the accelerated evolution. Taken together, our results suggest an important role that FOXP2 may have played in the origin of human speech and demonstrate a strategy for identifying candidate genes underlying the emergences of human-specific features.