The Information Commissioner's Office (ICO) was alerted to the data breach earlier this year following the loss of a compact disc passed to Virgin Media by Carphone Warehouse. The loss came to light in June.
The disc contained the personal details of individuals interested in opening a Virgin Media account in a Carphone Warehouse store.
Virgin Media has been ordered to implement a number of security measures to protect customers' personal information more effectively.
Virgin Media has been told to encrypt all portable or mobile devices which store and transmit personal information. Any company processing personal information on behalf of Virgin Media must also use encryption software. This must be clearly stated in all contracts.
The ICO has forced Virgin Media to sign a formal undertaking to comply with the principles of the Data Protection Act. Failure to meet the terms of the undertaking will lead to further action by the ICO.
Mick Gorrill, assistant commissioner at the ICO, said: "The Information Commissioner's Office takes all breaches of data security seriously. Customers must feel confident their personal information will be handled properly by an organisation and, importantly, that their details will not be accessed by a third party.
"The Data Protection Act clearly states that organisations must keep personal information secure. Virgin Media recognises the seriousness of this data loss and has agreed to take the immediate remedial action we outlined to protect its customers' personal details."