Adopting alternative business models is one way for mature businesses to generate new growth. Several studies have addressed some of the organizational barriers that incumbents face when developing such new business models, but our understanding of the organizational (re)design aspects inherent to business model innovation is still very incomplete. In this study, we investigate the organizational design challenges for incumbent organizations in mature industries when they need to reinvent their business model in reaction to disruptive changes in their environment. Our empirical setting focuses on national postal operators in the European postal industry. Using an inductive study of three such operators, we distinguish between two stages within business model innovation: namely, business model exploration and business model exploitation. Focusing on the former, our findings shed new light on the existence of four key organizational issues: (1) organizational conflicts for scarce resources, (2) cognitive limitations in the face of a persistent dominant logic, (3) organizational (re)design issues focused on structure, and (4) the sourcing and development of new capabilities. These four areas of organizational study have not received much attention yet in the growing literature on business model innovation and represent opportunities for further developing the literature