The regulations to support the Anti-Terrorism, Crime and Security Act propose a voluntary scheme whereby telecoms companies and ISPs keep records of telephone calls for one year and e-mail traffic for six months.
The regulations were announced as the government unveiled new powers that will give fire authorities, ambulance services, the Financial Services Authority and other government organisations access to e-mail traffic data.
Voluntary data retention is likely to be followed by a compulsory scheme, with the costs of data storage eventually being passed on to end-users, industry observers believe.
Cambridge University computer and privacy specialist Richard Clayton, said "Recording all this data is not cheap - this is going to push up the cost of the telcos, ISPs and mobile operators. In the long term, customers will pay."
A Home Office spokesman said, "We have to produce a balance between what is required to combat terrorism and what is reasonable to ask industry to deliver."