Business model innovation is undoubtedly of strategic importance in innovation management. However, little is known on how in fact how companies experiment and innovate with regards to their business models. To shed more light on this issue, we have conducted a qualitative study of the newspaper industry in Denmark. Business model innovation became imperative for the traditional newspaper publishers after many years of the declining readership and revenues. We collected rich primary and secondary data from various sources during 2010-2012. Our analysis suggests that changing business models in its various parts does not guarantee a successful business model change and may even harm the existing well-functioning business model. To innovate a business model successfully, managers need to secure the business logic flow and its feedback loops.