A Bovis spokesperson confirmed that the company had pulled out, and said it had informed the client of the move.
He said: "We are confident we will find another soft services provider. We are in discussions with other firms."
The spokesperson added that the move would not affect other PFI bids being undertaken by the two companies.
The Bovis team is in a two-horse race with Balfour Beatty for the hospital after Carillion withdrew its bid in January.
The Sodexho withdrawal comes a week after Amey pulled out of the Bovis team bidding for the £3bn Allenby and Connaught barracks redevelopment.