Jack Straw has ordered an inquiry into the loss of a computer hard drive containing the details of up to 5,000 employees of the justice system.
The justice secretary is also trying to establish why he was not told of the blunder, which happened in July 2007.
The details, of employees of the National Offender Management Service in England and Wales, including prison staff, were lost by private firm EDS.
Justice Minister David Hanson said he was "very angry" at the loss.
'Deeply regret'
"I await the enquiry to see the details of the information, but my assessment is that the confidentiality and the security of staff will, I hope, not be compromised," Mr Hanson told BBC Radio Five Live.
The minister said the loss was "something which I deeply regret and am very angry about as a minister".
But he also said it was "a historical loss which I do not believe will ultimately compromise the safety and security of those who work for us".
Earlier, fellow Justice Minister Michael Wills had said there had been too many incidents of data loss in the private sector and the public sector and that "had to stop".
"We're giving the information commissioner new powers, we're introducing new penalties for the reckless or knowing misuse of data. We have to see an end to this sort of incident," Mr Wills added.
'Level of risk'
The loss of the data by the private computing firm was reported to the Prison Service in July, but Mr Straw was not informed of the problem until now, after a letter about the missing drive was passed to the News of the World newspaper.
In a statement, Mr Straw said: "I am extremely concerned about this missing data.
"I was informed of its loss at lunchtime today (Saturday) and have ordered an urgent inquiry into the circumstances and the implications of the data loss and the level of risk involved.
"I have also asked for a report as to why I was not informed as soon as my department became aware of this issue.
RECENT LOSSES Nov 2007: 25m people's child benefit details, held on two discs Dec 2007: 7,685 Northern Ireland drivers' details Dec 2007: 3m learner drivers' details lost in US Jan 2008: 600,000 people's details lost on Navy officer's stolen laptop June 2008: Six laptops holding 20,000 patients' details stolen from hospital July 2008: MoD reveals 658 laptops stolen in four years
"My officials are also in touch with EDS as part of these processes. We take these matters extremely seriously."
The Ministry of Justice has contacted the Information Commissioner's Office about the incident and will update it on Monday.
Justice Minister, David Hanson explained the purpose of the investigation:
"That will look at both the information lost, how the information was lost and what subsequently happened in relation to reporting mechanisms through the prison system, and to ministers -- because obviously that is of concern."
The latest disclosure comes just weeks after the details of thousands of criminals, held on a computer memory stick, were lost by a private contractor.
Shadow justice secretary Nick Herbert said: "The records of prisoners have been lost already and now we discover that personal data about prison officers has gone too.
"When was this incompetent government planning to own up to another data disaster - this time one which has put the security of thousands of its own employees at risk - and if, as they claim, they didn't know about this until now, who on earth is actually running the department?"
The Prison Officers' Association said the loss, which it had not been informed about, could end up costing the taxpayer millions of pounds.
National chairman Colin Moses said: "We are extremely concerned that not only has this data been lost, but that the Prison Service appear to have tried to conceal this serious breach in security.
"It is a breach that we believe could ultimately cost the taxpayer millions and millions of pounds, because, if the information lost is personal and sensitive, it may well mean staff having to move prisons, move homes and relocate their families."