The Ministry of Defence and EDS are investigating the loss of a portable hard drive containing personal details of 100,000 military personnel and up to 600,000 potential recruits.
The unencrypted drive was found missing by EDS, the MoD's IT outsourcer, during an audit that was ordered by the Cabinet Office as part of an investigation into data security across Whitehall.
The investigation was ordered after government departments lost personal information on four million people in the last year.
The MoD drive contains names, addresses, passport numbers, dates of birth, driving licence details and telephone numbers -- vital information for identity thieves.
It is not clear yet whether the drive has been stolen or mislaid.
Last month the RAF defended its failure to encrypt data on three portable USB hard drives containing sensitive information that were stolen from the RAF Innsworth base in Gloucestershire.
The RAF said there was no need to encrypt the data because the drives were held in a "secure area".
In July, the Ministry of Defence revealed that 658 laptops have been stolen over the past four years. It had previously claimed that 347 laptops were stolen between 2004 and 2007.
Nick Lowe, regional director for security vendor Check Point said: "The security of detailed, personal data of this kind cannot be left to chance. Portable discs and data cannot be left unprotected by automatic encryption, because they will go missing, be misplaced, or get stolen."
This week HP announced plans to slash 3,378 jobs over two years following its acquisition of EDS.