Hand Foot and Mouth Disease (HFMD) constitutes a considerable burden for health care systems across China. Yet this burden displays important geographic heterogeneity that directly affects the local persistence and the dynamics of the disease, and thus the ability to control it through vaccination campaigns. Here, we use detailed geographic surveillance data and epidemic models to estimate the critical community size (CCS) of HFMD associated enterovirus serotypes CV-A16 and EV-A71 and we explore what spatial vaccination strategies may best reduce the burden of HFMD. We found CCS ranging from 336,979 (±225,866) to 722,372 (±150,562) with the lowest estimates associated with EV-A71 in the southern region of China where multiple transmission seasons have previously been identified. Our results suggest the existence of a regional immigration-recolonization dynamic driven by urban centers. If EV-A71 vaccines doses are limited, these would be optimally deployed in highly populated urban centers and in high-prevalence areas. If HFMD vaccines are included in China's National Immunization Program in order to achieve high coverage rates (>85%), routine vaccination of newborns largely outperforms strategies in which the equivalent number of doses is equally divided between routine vaccination of newborns and pulse vaccination of the community at large.