The contract, which will start on 1 December, will support a council-wide structured change programme, known as Transformation.
The aim is to save up to 40% of the revenue budget over the next ten years, with a series of business cases being developed over the course of the contract. The council says it will have the final decision on which changes to proceed with.
The contract will initially focus on the council's ICT, revenues, benefits and facilities services. Mouchel has been given the task of putting the standard of these services within the best 25% in the country by 2013, whilst also saving 5.9% a year on their running costs.
The council says it is hoped 650 new jobs in the private sector will created as a result of the deal, which includes those staff transferring over to Mouchel from the public sector. However, only 350 jobs are guaranteed contractually by Mouchel.
These jobs will include a number in the emerging field of carbon management, through the creation of a national "centre for excellence", and the regional provision of support services - such as IT and facilities management - to other public sector organisations.
Councillor Peter Charon, leader of the council, said, “This is probably the most significant decision council has taken for many years and it is not something that a single member has considered lightly.
In a series of four meetings over three days, the business case has been scrutinised, debated and ultimately accepted.”
The combination of service improvement, cost reduction, council-wide transformation, a flexible contract that lets the council maintain control, and added benefit to the wider economy made it "a once in a generation opportunity", said Charon.
The contract was approved by 34 votes to 12 on the council. The decision to award the contract came after the council learned that the government would be slashing its council grant to the borough by 11 percent next year, so making savings was very much on the agenda.
Council union Unison fought the deal and says 88 jobs from just over 300 being transferred will be lost.
Although the details of the contract are secret, it has emerged that the council can stop Mouchel being paid for work it does not do, but it cannot impose contract penalties.