Regional-level information on heavy metal pollution in agro-ecosystems is essential for food security because excessive levels of heavy metals in crops may pose risks to humans. However, collecting this information over large areas is inherently costly. This paper investigates the possibility of applying multi-temporal Sentinel-2 satellite images to detect heavy metal-induced stress (i.e., Cd stress) in rice crops in four study areas in Zhuzhou City, Hunan Province, China. For this purpose, we compared seven Sentinel-2 images acquired in 2016 and 2017 with in situ measured hyper-spectral data, chlorophyll content, rice leaf area index, and heavy metal concentrations in soil collected from 2014 to 2017. Vegetation indices (VIs) related to red edge bands were referred to as the sensitive indicators for screening stressed rice from unstressed rice. The coefficients of spatio-temporal variation (CSTV) derived from the VIs allowed us to discriminate crops exposed to pollution from heavy metals as well as environmental stressors. The results indicate that (i) the red edge chlorophyll index, the red edge position index, and the normalized difference red edge 2 index derived from multi-temporal Sentinel-2 images were good indicators for screening stressed rice from unstressed rice; (ii) Rice under Cd stress remained stable with lower CSTV values of VIs overall growth stages in the experimental region, whereas rice under other stressors (i.e., pests and disease) showed abrupt changes at some growth stages and presented “hot spots” with greater CSTV values; and (iii) the proposed spatio-temporal anomaly detection method was successful at detecting rice under Cd stress; and CSTVs of rice VIs stabilized regardless of whether they were applied to consecutive growth stages or to two different crop years. This study suggests that regional heavy metal stress may be accurately detected using multi-temporal Sentinel-2 images, using VIs sensitive to the spatio-temporal characteristics of crops.