Hand–foot–mouth disease due to enterovirus 71 (EV71) and coxsackievirus A16 (CA16) has recently caused large outbreaks in mainland China in 2008. We performed complete genome sequencing on two EV71 (SZ/HK08-5 and SZ/HK08-6) and two CA16 (SZ/HK08-3 and SZ/HK08-7) strains from patients in Shenzhen, China. Phylogenetic, similarity plot and bootscan analyses revealed recombination between EV71 genotypes B and C at the 2A–2B junction, and between EV71 genotype B and CA16 strain G-10 in the 3C region for EV71 strains. A similar phenomenon was also found upon further gene sequencing with other EV71 strains. Recombination between CA16 strain G-10 and EV71 genotype A at the 2A–2B junction was also observed for CA16 strains. The present “double-recombinant” EV71 strains circulating in China and other EV71 subgenotype “C4” strains represent an additional genotype, D. CA16 strains should also be classified into two genotypes. This represents the first evidence for a combination of intratypic and intertypic recombination in EV71 strains.