David Miliband has admitted two US 'extraordinary rendition' flights landed on UK territory in 2002.
The foreign secretary said in both cases US planes refuelled on the UK dependent territory of Diego Garcia.
He said he was "very sorry" to have to say that previous denials made in "good faith" were now having to be corrected.
The renditions - the transport of terror suspects around the world for interrogation - only came to light after a US records search, he said.
BBC world affairs correspondent Paul Reynolds said the revelations were "a serious embarrassment for the British government".
Former Foreign Secretary Jack Straw and former Prime Minister Tony Blair made statements in 2005, 2006 and 2007 saying there was no evidence that rendition flights had stopped on UK territory.
Mr Miliband said the US had told him that neither of the two men involved in the rendition were British, neither left the plane and the US had "assured" him that no US detainees were ever held on Diego Garcia and US records showed no other evidence of renditions through UK territory.
But he said he would compile a list of all flights in UK territory about which concerns had been expressed to send to the US for "specific assurance" they were not used for rendition.
One of the men involved has since been released and one is at Guantanamo Bay.
Mr Miliband said the UK had been told neither of them had been involved in "secret detention centres" nor were subject to water boarding "or other similar forms of interrogation".
He said US Secretary of State Condoleezza Rice shared his "deep regret" about the mistaken assurances.
"Extraordinary rendition" is the term used by US intelligence agencies when they send terror suspects for interrogation by security officials in other countries, where they have no legal protection or rights under American law.
The UK says it expects the US to seek its permission before rendering detainees through UK airspace or territory.
Later Prime Minister Gordon Brown said: "It is unfortunate that this was not known and it was unfortunate it happened without us knowing that it had happened but it's important to put in procedures [to ensure] this will not happen again."
He added: "We share the disappointment that everybody has about what's actually happened."
In the Commons, William Hague, the shadow foreign secretary, said he accepted assurances were made "in good faith" but said: "This information will cause widespread concern given the categoric nature of the assurances previously given.
"More worrying still, it means that very specific assurances about the use of the facilities at Diego Garcia have also turned out, although given in good faith, to have been false."
For the Lib Dems, Edward Davey called for a full inquiry and said extraordinary rendition was "state-sponsored abduction" and the government must ensure that Britain was not used to "facilitate" it.
Former Lib Dem leader Sir Menzies Campbell added: "The truth is, this is a gross embarrassment, in spite of its good faith, for the British government, involving as it does a breach of our moral obligations and possibly our legal responsibilities as well."
Labour MP Mike Gapes, chairman of the foreign affairs select committee, told MPs the US administration "has clearly misled or lied to our government, [which] has resulted in our government misleading... members of this House."
But Mr Miliband told the BBC later: "I do not believe the US government set out to mislead the British government. I believe they told us in good faith they had no evidence of the use of Diego Garcia."
He said British principles were "absolutely clear" - that it would not support the use of rendition for torture and always required permission for the use of British bases.
"I have it from the mouth of the Secretary of State of the US that that is understood at the highest levels of in the American government," he added.
Amnesty International UK director Kate Allen said extraordinary rendition was "a polite way of talking about kidnapping and secret detention".
"It is not enough for the government simply to accept US assurances on correct behaviour in the war on terror - we should retain our own integrity and act accordingly," she said.
In a statement CIA director Mike Hayden said neither of the two men on the flights "was ever part of CIA's high-value terrorist interrogation program" but said they would learn from their "errors".
He added that speculation about a CIA holding facility on Diego Garcia was "false" - as were allegations that detainees were transported to be tortured.
"Torture is against our laws and our values. And, given our mission, CIA could have no interest in a process destined to produce bad intelligence."