Human enteroviruses of species A (EV-A), including EV-A71, are the leading cause of hand-foot-and-mouth disease (HFMD) and may also cause severe neurological manifestations. We investigated the circulation and molecular evolution of EV-A in Madagascar, focusing particularly on the recently described EV-A71 genogroup F. Eight different types, collected mostly in 2011, were identified, highlighting the local circulation and diversity of EV-A. Comparative genome analysis revealed evidence of frequent genetic exchanges between the different types of isolates. The three EV-A71 isolates had different evolutionary histories in terms of recombination. The engineering and characterization of recombinants involving progenitors belonging to different EV-A types indicated a high degree of permissiveness for genetic exchange in EV-A. No outbreak of disease due to EV-A has yet been reported in Madagascar, but the diversity, circulation, and evolution of these viruses justify the surveillance of EV-A circulation to prevent possible HFMD outbreaks due to emerging strains.