Shrinking cities are a class of cities that show different trajectories in the urbanization process. Although many studies have examined shrinking cities from multi-dimensional perspectives, the spatiotemporal evolution of land use structure is still poorly understood. This study constructed an analysis framework for spatiotemporal evolution characteristics of land use structure over two 10-year periods based on 334 county-level administrative units in the context of northeast China, a region undergoing substantial population loss and urban shrinkage. This study analyses quantitatively measured population loss and land use conversion and investigated the rationality of the expansion mode of newly added construction land in research units. The results demonstrated that, first, the total population in northeast China continued to decline, but the total construction area continued to grow, and the various types of construction land in most shrinking units did not decline with the loss of population. Second, 67.09% of new construction land came from cropland, and compared with 2000–2010, the growth of new construction land in 2010–2020 slowed down. Third, during the study period, more than half of the expansion area for newly added construction land came from sprawling expansion, and areas in a state of shrinking were no exception.