Sporadic outbreaks caused by coxsackievirus A4 (CV-A4) have been reported worldwide. To further elucidate the detailed genetic characteristics and evolutionary recombination events of CV-A4, virus samples from nationwide hand, foot and mouth disease (HFMD) surveillance, encompassing 27 out of the 31 provinces in China, were investigated. Comprehensive and systematic phylogenetic analyses were performed by using 29 complete genomes, 142 complete CV-A4 VP1 sequences. Four genotypes (A, B, C and D) and five sub-genotypes (C1-C5) were re-identified based on the complete VP1 sequences. C2 is the predominant sub-genotype of CV-A4 associated with HFMD and has evolved into 3 clusters. Cluster 1 is a major cluster that has been persistently and extensively circulating in China since 2006 and has been associated with all severe cases. All the sequences showed high homology with the CV-A4 prototype in the P1 region, while higher identities with CV-A5, CV-14 and CV-16 in the P2 and P3 regions. Recombination analysis revealed that C2 had two specific genetic recombination patterns with other EV-A prototypes in the 5'-UTR and 3D region compared with C5. These recombination patterns might be associated with the increased transmissibility of C2 viruses, which were obtained due to their persistent and extensive circulation in populations.