Organizational leaders are often presented with novel, complex, and ill-defined problems that call for creative problem-solving. Furthermore, the socially embedded nature of leadership problems requires that leaders develop solutions in light of the needs, concerns, and perspectives of key organizational stakeholders. Put differently, to solve creative problems leaders must engage in effective sensemaking to understand the mental models of stakeholders. However, little research has investigated the impact of understanding stakeholders’ mental models on the creative performance of leaders. In this study, participants were asked to generate a solution to an educational problem. Prior to solution generation, however, they were presented with case information about three stakeholders and were asked to depict the mental model of each stakeholder. Findings indicated that a more accurate understanding of stakeholders’ mental models resulted in enhanced performance across multiple creative criteria. Additionally, it was found the successful execution of various cognitive sensemaking strategies was related to a more accurate understanding of stakeholders’ mental models. The implications of these findings for understanding and enhancing leadership performance in organizations are discussed.