The company is the favourite to win the £4bn-plus Aspire contract to run the Inland Revenue's IT systems. It is also expected to be a key bidder for contracts in the £2.3bn NHS IT modernisation and a £4bn to £5bn Ministry of Defence modernisation, announced earlier this week.
However, EDS has been rocked by problems with megadeals signed by Brown since his appointment in 1998.
Two key customers WorldCom and US Airways, filed for bankruptcy last year while problems involving deals with the UK's social security department and the US Navy resulted in delayed payments worth hundreds of millions of pounds.
The resulting profit warning and an investigation by US financial regulators contributed to the loss of a multibillion dollar outsourcing contract that Procter & Gamble was about to award it late last year.
Last month Brown was forced to open EDS' annual meeting with financial analysts with the news of the collapse of final negotiations with French engineering giant Alstom over a multibillion-dollar outsourcing contract.
Robert Morgan, chief executive of outsourcing advisers Morgan Chambers, said Brown's departure exemplified the "malaise that the outsourcing industry finds itself in".
Morgan said that Brown "epitomised the deal-centric obsession" of tier-one service companies such as EDS, IBM and CSC. These suppliers were losing business, he said, because of the lack of investment in the next generation of shared services.
Anthony Miller, research manager at analyst group Ovum Holway, said: "EDS, like everyone else, has been hit hard by the downturn in the market, but it is still one of the slickest outsourcers around and one of the few companies that can take on megadeals."
It was unlikely the EDS board would have let Brown go if it thought the move would affect the company's relationship with the UK government, which is a key customer.
Brown is being replaced as chairman and CEO by Michael Jordan, who retired as chairman and CEO of CBS in December 1998. The company is also bringing back Jeffrey Heller, who retired from EDS in February 2002 after 34 years with the company. He was EDS vice chairman at the time.