To address the myriad of challenges that they are confronted with, city governments turn to information and communications technology and seek to implement innovative smart city solutions. As they are typically not equipped to develop these solutions on their own, city governments often approach private sector companies. Whereas for traditional procurement projects, they commonly partner with incumbents, startups are relevant partners for smart city innovation projects due to their proximity to the latest technological developments. However, as existing literature predominantly treats private companies as a uniform group, city governments are largely left in the dark when selecting the most suitable private-sector partners. Based on an analysis of six case studies, this study illustrates that startups and incumbents can play complementary roles in public-private co-creation projects for innovative smart city solutions. Moreover, it introduces a framework for how city governments can involve both startups and incumbents and thus leverage their differences.