The US State Department, acting "out of an abundance of caution," said 19 diplomatic outposts would be shuttered through Saturday.
Britain said its embassy in Yemen would remain closed until the end of the Muslim festival of Eid, the climax of the holy month of Ramazan, "due to continuing security concerns."
France also said its mission there would remain shut until Thursday.
Eid is due to end at the weekend.
On Saturday, the global police agency Interpol added to fears by issuing a security alert over hundreds of militants freed in jailbreaks.
The US closure list includes 15 embassies or consulates that were already shut on Sunday due to security fears, as well as four additional posts.
At least 25 US missions had initially been ordered closed.
US lawmakers on Sunday said the move was prompted by electronic intercepts of high-ranking al Qaeda operatives signaling a major attack.
The intercepts were "probably one of the most specific and credible threats I've seen, perhaps, since 9/11," said Michael McCaul, chairman of the House Homeland Security Committee.
An attack appeared to be "imminent," possibly timed to coincide with the last night of Ramazan, McCaul told CBS.
Saxby Chambliss, vice chairman of the Senate Intelligence Committee, said there has been "an awful lot of chatter" among terrorists about planning an attack, all "very reminiscent of what we saw pre-9/11".
Chambliss, appearing on NBC's "Meet the Press," said a National Security Agency program that electronically intercepts mobile phone and e-mail communication helped gather intelligence about this threat.
The NSA programs have come under intense scrutiny since former intelligence analyst Edward Snowden leaked information to the press about the scope of the surveillance.
"If we did not have these programs then we simply wouldn't be able to listen in on the bad guys," said Chambliss, who described the information as "the most serious threat that I've seen in the last several years."
ABC News cited an unnamed US official as saying there was concern that Al-Qaeda might deploy suicide attackers with surgically implanted bombs to evade security.
The diplomatic posts to be closed through Saturday included those in: Abu Dhabi, Amman, Cairo, Riyadh, Dhahran, Jeddah, Doha, Dubai, Kuwait, Manama, Muscat, Sanaa, Tripoli, Antananarivo, Bujumbura, Djibouti, Khartoum, Kigali, and Port Louis.
The new closures are located in Madagascar, Burundi, Rwanda and Mauritius.
The outposts that are reopening include those in Afghanistan, Algeria, Bangladesh, Mauritania, Iraq, and Israel.
The office of EU foreign affairs chief Catherine Ashton said European missions were liaising closely with their US allies and that "all necessary precautions are being taken."
Security was especially tight in Yemen's capital Sanaa on Sunday where Britain, France and Germany also shut their embassies.
Soldiers with armored personnel carriers were stationed outside the buildings as police and army checkpoints went up on all the city's main thoroughfares.
Residents said they heard the sound of a drone overhead, which could only be American as Washington is the sole power to operate the unmanned aircraft in the region.
The United States considers al Qaeda in the Arabian Peninsula to be the network's most active and dangerous branch, and has waged an intensifying drone war against AQAP militants in Yemen.
Although Washington has responded to terrorist threats before by closing diplomatic missions, this was believed to be the most widespread closure ever.
Interpol said it suspected al Qaeda was involved in breakouts in nine countries, notably Iraq, Libya and Pakistan, that had "led to the escape of hundreds of terrorists and other criminals."
The State Department late last week issued a worldwide travel alert to US citizens, warning of the "potential for terrorists to attack public transportation systems and other tourist infrastructure."
Washington has been especially cautious about security abroad since an attack on its consulate in the Libyan city of Benghazi on September 11 last year.
Ambassador Chris Stevens and three other Americans were killed in the attack blamed on militants.
COMMENTS (3)
Comments are moderated and generally will be posted if they are on-topic and not abusive.
For more information, please see our Comments FAQ
Is this all a drama or is something really going on?
@Toba Alu: US operates differently from PAkistan. This is not like the 1 day cellphone stoppage that Rehman MAlik ordered after which it was business as usual. During the time that the consulates are closed, US will use all their intelligence assets in identifying and neutralising this Al Qaeda threat. The consulates will not reopen until such time as that goal is achieved.
Al Qaeda has the time. These closures are just futile. More likely it is to convince the world that to continue monitoring our e-mails and listing to our telephone calls is justified.