This study investigates how large incumbent organizations navigate paradoxical tensions of innovation. As business environments become increasingly uncertain, firms are required to adopt agile ways of working to promote creativity and provide innovative solutions to customers’ evolving needs. However, this often generates considerable tensions with existing processes and practices aimed at ensuring control and efficiency. We use extensive interviews and archival data collected in 20 large, highly regulated companies that recently implemented design thinking to become more used-centered and innovative. We uncover three paradoxes: playfulness vs. pressure to deliver; autonomous decision-making vs. hierarchy and organizational structure; and user needs vs. organizational goals. For each paradox, we identify similar dynamics and four fundamental aspects. This study extends research on paradox theory, innovation, and creativity by showing how the introduction of innovative approaches, such as design thinking, can make paradoxes more salient, and by identifying practices that can help organizations navigate them. Specifically, it highlights the benefits of adopting structured processes comprising of diverging and converging elements, promoting cross-functional collaboration, and using visual artifacts to facilitate interactions among multiple parties. However, it also emphasizes the importance of balancing novel practices with existing ones, adopting a paradoxical frame whereby opposing aspects are nourished.