The council said the move, in the contract's fourth year, was necessary to deal with criticism from the Audit Commission, the local government watchdog.
"Our legal advice is that it [HBS] has committed actionable breaches. We have communicated very precisely the nature of the problems," said the council's deputy chief executive, Jonathan Flowers.
HBS is contesting the council's claims. "HBS denies that it has committed any actionable breach whatsoever. Furthermore, it is apparent that the decision to terminate the partnership agreement is being treated by the council as a fait accompli," it said.
HBS administers and manages IT systems for all Bedfordshire's key services, including its IT department, call centre, HR department, social services and education departments. Neither Flowers nor HBS would confirm what parts of the outsourcing contract were being disputed.
The council's management began to report problems after HBS implemented a SAP ERP system in April 2003. It failed to publish its accounts for 2003/04 before its legal deadline of 30 November 2004.
In his latest annual audit letter, the independent district auditor said, "The strategic partnership is not delivering improvements in services."
HBS has three other large outsourcing customers - Lin colnshire County Council, Middlesbrough Council and Milton Keynes.