Sustainability has been at the forefront of procurement policy in the UK in recent years, and innovation can be a key constituent to deliver the sustainability agenda. This paper uses a single case study to illustrate the procurement of recycled paper by a UK government department. It charts the transformation in procurement from that of a product to an integrated service, and highlights the procurement of a sustainable innovation to achieve multiple objectives. The study indicates the importance of certain factors for enabling the procurement of a more innovative and sustainable solution. In particular it illustrates the role of project champions driving change, senior management support, a good working relationship between buyer and supplier and the creation of a space in which trust and ideas generation can be enabled. Data is drawn from secondary sources, observations and in-depth interviews with public and private stakeholders participating in the process.