The US state department said it had pulled all non-essential personnel from Yemen, and the Pentagon said the US Air Force had flown staffers out.
Two US military planes carrying as many as 90 Americans from Yemen were en route to Ramstein Air Base in Germany, CNN reported.
"In response to a request from the US state department, early this morning the US Air Force transported personnel out of Sana'a, Yemen, as part of a reduction in emergency personnel," Pentagon press secretary George Little said.
"The US department of defence continues to have personnel on the ground in Yemen to support the US state department and monitor the security situation," Little said.
The US earlier ordered reduction of embassy staff in Yemen issuing a fresh travel warning of a high security threat level due to terrorist activities and civil unrest.
The alert came hours after a drone attack killed four Al Qaeda militants in Yemen and two days after the closure of some two dozen embassies in the Middle East and Africa.
"The Department of State ordered a reduction in the number of emergency US government personnel in Yemen," state department spokesperson Jen Psaki said in a statement.
"We are concerned about a threat stream indicating the potential for terrorist attacks against US persons or facilities overseas, especially emanating from the Arabian Peninsula," she said.
US citizens remaining in Yemen despite the travel warning in effect should limit non-essential travel within the country, she said.
Meanwhile, the British government said it flew the embassy staff in Sanaa back to London overnight.
"Due to increased security concerns, all staff in our Yemen embassy have been temporarily withdrawn, and the embassy will remain closed until staff are able to return," the Foreign and Commonwealth Office said in a statement on Tuesday.
The Foreign and Commonwealth Office had already announced the closure of its embassy in Sanaa until the end of the festival of Eid amid the global terror alert.
The US issued the worldwide alert linked to Zawahiri's intercepted conversations with his deputy in the Arabian Peninsula and ordered closure of several American diplomatic missions in the region.
The intercepted message last week between Zawahiri and Nasser al-Wuhayshi, the head of the Yemen-based Al Qaeda in the Arabian Peninsula, revealed one of the most serious plots against American and Western interests since the attacks on September 11, 2001, the New York Times reported.
"Zawahiri ordered the leader of Al Qaeda's affiliate in Yemen to carry out an attack as early as this past Sunday," the paper quoted American officials as saying.
The paper said that no targets had been singled out in the talks, but that a possible attack appeared to be imminent.
The Al Qaeda leader sent the message to Wuhayshi telling him to "do something".
US intelligence believes al-Wuhayshi has recently been appointed the overall terror organisation's No. 2 leader.
The US closed 22 missions across the Middle East on Sunday and extended the closures of 19 of them till August 10.
Image: A police trooper is seen manning a checkpoint in Sanaa on Monday.
Photograph: Khaled Abdullah/Reuters
Al Qaeda threat forces US to shut 22 embassies
Al Qaeda in Arabian Peninsula gaining strength: US
Future of flying: Solar-powered planes?
Syria conflict will go on till its bitter end
19 US mission in the Muslim world to stay shut