For years the US and Britain have relied on Yemen's strongman President Ali Abdullah Saleh to fight al-Qaeda in the Arabian Peninsula - a regional offshoot of the terror group, which Washington says poses the biggest threat to the US domestic security.
But for months Yemen has been the scene of widespread unrest and Mr Saleh the subject of protests against his leadership.
President Saleh has been in power in Yemen since 1978
Mr Saleh, who has led Yemen since 1978, has this week accepted a plan put forward by the Gulf Arab states for him to hand over power, but the protests have continued.
The uprising against the United States' old ally not only undermines US counter-terrorism efforts, it also raises some serious questions about choices that Washington has made in Yemen.
Since the unrest began Mr Saleh has warned that if he resigned Yemen would fall into the hands of extremists.
He has dubbed the protests an attempt to stage a coup against his rule and claimed that they could result in civil war.
That is feeding into the very fear that has shaped US policy on Yemen.
In the last decade the US gave the Yemeni government hundreds of millions of dollars worth of military aid to counter-terrorism troops under the command of the president's son and nephews.
"Very quickly the government realised that terrorism was actually a very profitable business," says Sanaa based analyst Abdel Ghani al Iriyani. "Americans should have never bought into the ploy that the government actually wanted to fight al-Qaeda."
Mr al-Iriyani, like many here, argues that it would have been much wiser to spend the money on development instead.
More than 130 people have been killed since the unrest began in January
But throughout the last decade, military aid continued to grow, even though by 2008, US diplomats were warning Washington that Mr Saleh was using the assistance to quell political dissent.
For many Yemenis US military assistance became synonymous with the lack of political freedom.
Kemal Sharif, who is a political cartoonist, was arrested in August 2010 when US-trained anti-terror units stormed his house in central Sanaa.
"I thought I was in a movie about American marines in Iraq. Snipers were everywhere," Mr Sharif says of the raid.
The floor of his flat still has bullet marks, and his five-year-old daughter still cries when she remembers the evening her father was taken.
Mr Sharif was accused of having links with al-Qaeda, but never charged. He showed me what he thinks was the real reason for his arrest - colourful caricatures that make fun of the president and corruption, poverty and repression under his rule.
Lack of action
After four months in jail, including 50 days in solitary confinement, Mr Sharif was released on a condition that he would stop drawing the president.
He now has a personal grudge against the US: "Even my handcuffs said 'made in the United States'," he says.
Political cartoonist Kemal Sharif now holds a grudge against the US
Many in Yemen share his frustration with the US.
"Where is President Obama now? He is obsessed with al-Qaeda but why does he trust the lies that our president tells him and not the people," one young protester called Khaled told me.
While supporting the popular uprisings in Egypt and in Libya, President Barack Obama has been much more cautious about backing the Yemeni uprising.
The US has been working with the European Union and the Gulf Arab states to push for the deal in which the president will gradually transfer power, but the White House has not called on Mr Saleh to step down.
"I think the reason Washington is not clear on what they are doing, is because they don't know what they are doing," says Charles Schmitz, Yemen expert at Towson University.
Nobody likes al-Qaeda, but people join because they are poor, because they hate the government. If America helps us to get rid of Saleh, we'll help it to get rid of al-Qaeda
Khaled, Yemeni tribesman
Mr Schmitz says that a focus on security instead of development, coupled with lack of general expertise on Yemen and overall failure to develop meaningful relationships with anyone outside Mr Saleh's government, have left Washington unprepared to deal with the crisis.
Another problem, he says, is the US obsession with stability.
"A bit of instability may not be a bad thing, they should allow people to work out their relationships and they need to accept that Yemen simply governs in a different way," he says.
Mr Saleh has always said that ruling Yemen was like dancing on the heads of snakes, that only he could deal with tribal rivalries. For three decades, he ruled by playing tribes off against each other.
Yemen's uprising has created the most unlikely alliances. In one of the tents in Sanaa's Change Square, I found rival tribesmen from Marib, an area which is known as one of the safe heavens for al-Qaeda, discussing problems of their region.
They say that America's support for Mr Saleh has in fact fuelled the al-Qaeda threat.
"Nobody likes al-Qaeda, but people join because they are poor, because they hate the government," says Khaled, a young tribesman. "If America helps us to get rid of Saleh, we'll help it to get rid of al-Qaeda."
Khaled's region has come under attack - since 2009 the US has fired at least four missiles into Yemen, but they killed more civilians then militants.
The White House has refused to discuss its strategy on Yemen, but former US ambassador to Yemen Edmund Hull admits that it is hard to call it a success.
"We have failed to eliminate top al-Qaeda leadership in Yemen, and from that point of view our approach has not been successful," he said.
It is partly a result of the US policy on Yemen that whatever government eventually emerges from the political stalemate is very likely to be more populist and less accommodating to the US interests in Yemen.
The US is worried, but Yemeni protesters and politicians say that respecting choices made by the people could prove the most effective way of fighting the war on terror.
This page is best viewed in an up-to-date web browser with style sheets (CSS) enabled. While you will be able to view the content of this page in your current browser, you will not be able to get the full visual experience. Please consider upgrading your browser software or enabling style sheets (CSS) if you are able to do so.