The presence of UK armed forces in Iraq "exacerbates the security problems" and they should "get out some time soon", the head of the British Army has said.
Chief of the General Staff Sir Richard Dannatt told the Daily Mail that the military campaign fought in 2003 had "effectively kicked the door in".
He also said that initial planning for the post-war period had been poor.
There are currently more than 7,000 British soldiers in Iraq, based largely in Basra in the south of the country.
A Ministry of Defence spokesman said Britain had "a clear strategy" and worked with international partners "in support of the democratically elected government of Iraq, under a clear UN mandate."
BBC political editor Nick Robinson described Sir Richard's remarks as "quite extraordinary".
He said the new head of the British army's comments "directly contradicted so much of what the government had said".
Sir Richard might be issuing a "very public warning" to the next prime minister, our correspondent added.
In his interview, Sir Richard added that any initial tolerance "has largely turned to intolerance. That is a fact".
Sir Richard, who took on his role in August, also said planning for what happened after the initial successful war military offensive was "poor, probably based more on optimism than sound planning".
'Not invited in'
He said: "I don't say that the difficulties we are experiencing round the world are caused by our presence in Iraq but undoubtedly our presence in Iraq exacerbates them."
Most of the British forces in Iraq are based in Basra
Sir Richard told the newspaper: "We are in a Muslim country and Muslims' views of foreigners in their country are quite clear.
"As a foreigner, you can be welcomed by being invited in a country, but we weren't invited certainly by those in Iraq at the time."
He added: "Whatever consent we may have had in the first place, may have turned to tolerance and has largely turned to intolerance."
Downing Street issued a short statement in response to the general's comments.
It said: "It's important that people remember that we are in Iraq at the express wish of the democratically elected Iraqi government, to support them under the mandate of a UN resolution."
However, Sir Richard has received praise for coming forward.
Major General Patrick Cordingly said: "I think it is a very brave thing for him to say. I do agree. I think there comes a time when you have got to let Iraq get on and look after its own security."
Rose Gentle, whose soldier son was killed in Iraq, said: "I'm just really delighted that Sir Richard Dannatt has stood up and spoken out. He is protecting our boys.
"We have been saying for two years this needed to happen and I think military families have done a good bit."