Innovation of public service delivery is currently high at the political agenda in many countries – also within public libraries. Due to the development of digital technologies it is now possible for everybody (with access to the technology) to get access to all kinds of sources of information. In this way the digital development points at the question whether or not libraries have become redundant and must be regarded as a survival from a past society. In 2010 a new strategy for public libraries in Denmark set the goal that the library sector must reinvent the role of libraries to match the needs of library users in our contemporary society (Agency for Library and Media, 2010). The strategy stresses that one way to do this is to create innovative partnerships with external partners from the civic society, the private sector, or other public agencies. Even though the strategy sounds simple it raises some serious questions like: What is an ‘innovative partnership’, and how do we understand this phenomenon conceptually? How to implement the strategy and establish and work with such partnerships in practice? After the announcement of the strategy it became clear that the implementation of it is not at all simple and in practice it is quite complicated for a public library to engage in innovative partnerships with external partners. Hence, a project was set up to investigate the drivers and barriers for innovative partnerships and shape a model which public libraries can follow in their work with partnerships. The project was called: ‘Out of the Box’ and was running from 2010 to 2012. Given the results from ‘Out of the Box’ this paper will investigate how partnerships between libraries and external partners can serve as a vehicle for innovation. The paper is structured like this: First, I will present the ‘Out of the Box’ project and along with this I will introduce my methodology and empirical material. Second, I will investigate the concept of ‘innovative partnerships’. I will do this both in a theoretical and an empirical way. Third, I will present an analysis of the implementation of the strategy and discuss how partnerships can serve as a vehicle for innovation in the public sector. Finally, I will conclude by answering the above presented research questions.