Home Secretary Jacqui Smith has apologised after it emerged that government figures on foreign workers were underestimated by 300,000.
She admitted it was "bad" that the wrong figures were given out on foreign nationals since 1997, but said 2.7m new jobs had been created under Labour.
The number of foreign workers in the UK since 1997 is now thought to be 1.1m, not the 800,000 officially recorded.
For the Tories, Chris Grayling said it was an "extraordinary development".
Work and Pensions Secretary Peter Hain has written to his Tory and Lib Dem counterparts to apologise and admit that incorrect figures were given in Commons answers. He said the new figures were the "most robust estimate available".
The extra 300,000 was found after analysis of the Labour Force Survey, which is compiled by the Office for National Statistics, showed 8% of the UK's 29.1m workforce was foreign.
The revised figures relate to new jobs that have been created over the last 10 years.
The Department for Work and Pensions (DWP) stressed that ministers had used the earlier 800,000 estimate "in good faith".
It said the change would affect previous government responses on how many of the 2.7m jobs created since Labour came to power in 1997 have gone to British workers.
It had been said 2m had gone to British workers, but the government has admitted that was now "not technically accurate".
Ms Smith told the BBC: "Of course it is bad that these figures are wrong and ministers have apologised for that, I am sorry about that.
"But the important point is that actually there are 2.7 million more jobs in this country than there were in 1997.
"That's more jobs, yes, that have been filled by those that have come from abroad, but many more jobs that have been filled by UK nationals, and vacancies still out there for UK nationals."
Ministers do not know where foreign national workers are from
She added that a points-based system for migrant workers would be introduced next year, to ensure "stronger control" over those coming to the UK.
The government also agreed on Tuesday to continue imposing restrictions on the number of unskilled Romanian and Bulgarian workers coming to the UK until "at least the end of 2008". Previously it had adopted an "open door policy" towards Eastern European migrants.
Mr Grayling said the government's admission called "into question the competence of ministers and of the government as a whole".
Liberal Democrat work and pensions spokesman Danny Alexander said: "Getting these figures so wrong further undermines the credibility of the government's claims to be able to deliver a well-managed system for foreign workers."
A DWP spokesman said just under half the 1.1m foreign workers were EU nationals, while the remainder came from non-EU and Commonwealth countries, including the US, Australia, Canada, New Zealand and South Africa.
The revised figures only emerged after Tory shadow work and pensions minister James Clappison submitted a series of written parliamentary questions.
The employment minister, Caroline Flint, said some groups had been left out of the figures by mistake.
"That would include, for example, foreign nationals who are married to British people in this country, and also it included those foreign nationals who were not in employment pre-'97 who then subsequently went into employment.
Sir Andrew Green, chairman of campaign group Migration Watch, said a fixed limit on immigration numbers was now essential, amid projections of a sharp rise in Britain's population.
"Ten million projected in the next 25 years, 10 times the population of Birmingham - I mean, it's frankly ridiculous," he said.
"Arguments about the labour market and so on are completely secondary. What we have to consider is our quality of life and even more important our cohesion as a community and we just cannot take in 10 million people."
Labour MP Keith Vaz, who chairs the Home Affairs Select committee, said it was "astonishing" that such a mistake had been made when governments are expected to "give accurate figures to the public especially in a very tough and emotive area such as immigration".
He called on the government to ensure that the figures were accurate in future.