The admission came from the foreign secretary, David Miliband, who apologised to MPs for wrong information given by his predecessor Jack Straw and former prime minister Tony Blair.
Miliband said the government had recently received information from Washington that two flights - one to Guantánamo Bay and one to Morocco - stopped over at Diego Garcia, the British overseas territory in the Indian Ocean.
"Contrary to earlier explicit assurances that Diego Garcia had not been used for rendition flights, recent US investigations have now revealed two occasions, both in 2002, when this had in fact occurred," Miliband told MPs.
He said he had discussed the issue with the US secretary of state, Condoleezza Rice.
"We both agree that the mistakes made in these two cases are not acceptable, and she shares my deep regret that this information has only just come to light," Miliband said.
Gordon Brown, speaking in Brussels, said he shared "the disappointment that everybody has" about the rendition flights issue.
The prime minister told reporters: "We have just been informed by the United States of America about what has actually happened. The US has expressed regret for us not knowing about this issue. We share the disappointment that everybody has about what's actually happened."
There have been long-standing suspicions that the CIA has used one of its so-called "black site" prisons on Diego Garcia, home to a large US military base, to hold suspects, although Miliband today assured MPs that no US detainees have ever been held on Diego Garcia.
Miliband has been told by the US that neither of the men in the rendition flight to Diego Garcia was British. One is currently in Guantánamo Bay and the other has been released.
SCROLL TO CONTINUE WITH CONTENT
Never Miss a Beat.
Get our best delivered to your inbox.
The foreign secretary said an "error in the earlier US records search meant that these cases did not come to light".
Reprieve, a legal charity that represents a number of detainees at Guantánamo Bay, has in the past accused the government of cooperating with the US on extraordinary rendition - the practice of seizing terrorism suspects and interrogating them on non-US territory.
President George Bush acknowledged in September 2006 the existence of the CIA's black site prisons. He said al-Qaida suspects or members of the Taliban who "withhold information that could save American lives" have been taken "to an environment where they can be held secretly, questioned by experts".
Bush did not disclose the location of any prison, but suspicion that one may have been located on Diego Garcia, around 1,000 miles off Sri Lanka's southern coast, has been growing for years.
The 2,000 islanders were expelled in the early 1970s after the British government struck a secret deal to lease the 37 mile-long island to the US military.
Barry McCaffrey, a retired four-star US general who is professor of international security studies at the West Point military academy, has twice spoken publicly about the use of Diego Garcia as a detention centre for suspects.
In May 2004, he said: "We're probably holding around 3,000 people, you know, Bagram airfield, Diego Garcia, Guantánamo, 16 camps throughout Iraq." In December last year he repeated the claim.
The registration number of a Gulfstream executive jet has been linked to several CIA prisoner operations that flew from Washington to Diego Garcia, via Athens, on September 11 2002, soon after the capture of Ramzi Binalshibh, a suspected planner of the September 11 attacks.
A European investigator said last year he had proof that Poland and Romania hosted secret prisons for the CIA in which it interrogated top al-Qaida suspects using methods akin to torture.
British police said they had found no evidence to support claims that CIA planes transporting terrorism suspects to face possible torture in secret prisons in Europe had landed illegally at British airports.
© 2008 The Guardian