The transformation of shrinking cities has affected the coordination of the economy, society, and environment. This study explored the impact of urban shrinkage on eco-efficiency in cities in Northeast China in the period 2012–2019. Additionally, factors including industrial-structure upgrades, technological innovation, and land-use structure were introduced into the model to explore the mediating effect of urban shrinkage on eco-efficiency. Results revealed that urban shrinkage significantly negatively affected eco-efficiency. Moreover, urban shrinkage had a mediating effect on eco-efficiency through technological innovation and land-use structure, while urban shrinkage has a positive effect on eco-efficiency through industrial-structure upgrades. The robustness of these empirical results was also demonstrated by replacing variables. The underlying mechanism through which urban shrinkage affects eco-efficiency is rather complex, and governments should take a systematic approach to promoting the sustainable development of shrinking cities.