The system, which will be implemented by next March, will give all NHS workers a personal mailbox and access to online calendars and a national directory.
EDS claimed the implementation would be one of the largest corporate directory and e-mail service provisions in the world.
"This is a critical element in the NHS Information Authority's work to develop an efficient infrastructure for the NHS," said Carrie Armitage, the NHS Information Authority's head of access to information.
The system will be developed further to include instant messaging, Internet access, and remote access via mobile phones and personal digital assistants (PDAs).
Services will run across the NHS's network, NHSnet, and the Internet. Work at four early adopter sites is under way.
News of the NHS deal came as the Inland Revenue admitted its online self-assessment service, also run by EDS, could not cope with demand.
It also coincided with the news that EDS shareholders have launched legal action against the company following a profit warning earlier this month.