Smart city initiatives are being promoted across the world to address major urban challenges, and they all share a common belief in the transformative power of digital technologies. However, the pace of innovation in smart cities seems to be much slower than the rapid and profoundly disruptive transformations brought about by digital innovation in many other domains. To develop new insights about the main causes behind this relatively modest success, this study provides a Systematic Literature Review (SLR) on the connection between major smart city challenges and the essential properties of digital innovation. The review involved the qualitative analysis of 44 research papers reporting on smart city innovation practices and outcomes. The results characterize five major challenge categories for smart city innovation: Strategic vision; Organizational Capabilities and Agility; Technology Domestication; Ecosystem Development; and Transboundary Innovation. This study also explores the connections between these challenges and concrete digital innovation practices in smart city initiatives. The main conclusion is that current innovation practices in smart cities are not properly aligned with what the research literature commonly describes as core properties of digital innovation and that this might be a major cause behind the limited progress in smart city initiatives.