Organizations are often challenged to find new ways of creating and capturing value to compete with new entrants and disruptive technologies. Several studies have addressed some of the organizational barriers that incumbents face when developing 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 (re)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 case study 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 terms of a persistent dominant logic, (3) design of organizational structure, and (4) the sourcing and development of new capabilities.