Knowledge of the area and spatial distribution of paddy rice is important for assessment of food security, management of water resources, and estimation of greenhouse gas (methane) emissions. Paddy rice agriculture has expanded rapidly in northeastern China in the last decade, but there are no updated maps of paddy rice fields in the region. Existing algorithms for identifying paddy rice fields are based on the unique physical features of paddy rice during the flooding and transplanting phases and use vegetation indices that are sensitive to the dynamics of the canopy and surface water content. However, the flooding phenomena in high latitude area could also be from spring snowmelt flooding. We used land surface temperature (LST) data from the Moderate Resolution Imaging Spectroradiometer (MODIS) sensor to determine the temporal window of flooding and rice transplantation over a year to improve the existing phenology-based approach. Other land cover types (e.g., evergreen vegetation, permanent water bodies, and sparse vegetation) with potential influences on paddy rice identification were removed (masked out) due to their different temporal profiles. The accuracy assessment using high-resolution images showed that the resultant MODIS-derived paddy rice map of northeastern China in 2010 had a high accuracy (producer and user accuracies of 92% and 96%, respectively). The MODIS-based map also had a comparable accuracy to the 2010 Landsat-based National Land Cover Dataset (NLCD) of China in terms of both area and spatial pattern. This study demonstrated that our improved algorithm by using both thermal and optical MODIS data, provides a robust, simple and automated approach to identify and map paddy rice fields in temperate and cold temperate zones, the northern frontier of rice planting.