Human enterovirus 71 (EV-71) is one of the major etiologic causes of hand, foot, and mouth disease (HFMD) among young children worldwide, with fatal instances of neurological complications becoming increasingly common. Global VP1 capsid sequences (n = 628) sampled over 4 decades were collected and subjected to comprehensive evolutionary analysis using a suite of phylogenetic and population genetic methods. We estimated that the common ancestor of human EV-71 likely emerged around 1941 (95% confidence interval [CI], 1929 to 1952), subsequently diverging into three genogroups: B, C, and the now extinct genogroup A. Genealogical analysis revealed that diverse lineages of genogroup B and C (subgenogroups B1 to B5 and C1 to C5) have each circulated cryptically in the human population for up to 5 years before causing large HFMD outbreaks, indicating the quiescent persistence of EV-71 in human populations. Estimated phylogenies showed a complex pattern of spatial structure within well-sampled subgenogroups, suggesting endemicity with occasional lineage migration among locations, such that past HFMD epidemics are unlikely to be linked to continuous transmission of a single strain of virus. In addition, rises in genetic diversity are correlated with the onset of epidemics, driven in part by the emergence of novel EV-71 subgenogroups. Using subgenogroup C1 as a model, we observe temporal strain replacement through time, and we investigate the evidence for positive selection at VP1 immunogenic sites. We discuss the consequences of the evolutionary dynamics of EV-71 for vaccine design and compare its phylodynamic behavior with that of influenza virus.