Terrorists are plotting to use new stealth bombs in laptops and even humans to bring down a US-bound passenger plane, it is feared.
Airport security was increased across the UK, US and other countries amid fears al-Qaeda bomb experts have successfully designed a new explosive that can bypass current checks.
Airlines brace for security turbulence
Obama gives Bill Clinton the hurry-up
Van Gogh paintings found in Naples farmhouse
Clinton calls Trump's beauty queen tweets 'unhinged'
Girl rescued from rubble in Aleppo
Aussie turntablist dares to dream
Listen to the SMH Live - US Election event
Hillary Clinton: Trump 'violated' Cuban embargo
Airlines brace for security turbulence
Airport security increases across Europe after a US warning that two terror networks are working together on a bomb.
They are believed to be targeting the thousands of Western jihadists fighting in Syria and Iraq as would-be suicide bombers.
The threat, which originated from US intelligence, has had an immediate impact at British airports, where passengers were subjected to more stringent and rigorous security checks.
It raises the prospect of a summer of delays and chaos for holidaymakers with long queues at airports.
The British Prime Minister said the safety of passengers “must come first” while Deputy PM Nick Clegg warned travellers the new checks would be a permanent feature.
Changes to security measures were announced after the secretary of the US Department of Homeland Security, Jeh Johnson, ordered beefed-up security at foreign airports which have direct flights to the US.
There are concerns that al-Qaeda terrorists in Yemen, known as al-Qaeda in the Arabian Peninsula (AQAP), and specifically its master bomb maker Ibrahim Hassan al-Asiri, have linked up with the Jabhat Al-Nusra jihadists in Syria and passed on bomb making skills.
It is feared a new type of explosive has been developed that will not be picked up under normal checks.
It remains unclear whether that could be deployed in an electronic item such as a laptop, a liquid based explosive soaked on clothing or even surgically implanted in a bomber.
All such techniques have been tried by Asiri in the past.
At Heathrow, passengers were being asked to turn on laptops, mobile phones and other electronics as they passed through security.
Staff were also swabbing all electronic items, clothing and shoes to check for traces of explosives.
Shoes and belts had to be removed and travellers were subject to “vigorous" physical searches, according to one passenger.
Mr Cameron said: "We take these decisions looking at the evidence in front of us and working with our partners.
"This is something we've discussed with the Americans and what we have done is put in place some extra precautions and extra checks.
"The safety of the travelling public must come first. We mustn't take any risks with that.
"I hope this won't lead to unnecessary delays but it's very important that we always put safety first, and we do."
A Department for Transport spokesman said: "We have taken the decision to step up some of our aviation security measures. For obvious reasons, we will not be commenting in detail on those changes.
"The majority of passengers should not experience significant disruption."
But Mr Clegg said that the new checks were unlikely to be "a one-off, temporary thing".
"This is the world we now live in," he said.
"I don't want people to think that this is some sort of blip for a week. This is part of an evolving and constant review about whether the checks in our airports – and indeed other places of entry and exits from countries – keep up with what we know from intelligence and other sources about the nature of the threats we face."
The threat centres on the thousands of Western jihadists, including hundreds of Britons, who are fighting in Syria and Iraq.
It is feared they will be taught bomb-making skills by Asiri and AQAP and then sent back to target planes.
Asiri was the mastermind behind an underwear bomb that failed to detonate aboard a jet over Detroit on Christmas Day 2009 and a more sophisticated version which was intercepted in a CIA sting operation three years later.
He also designed the powerful bomb hidden in printer ink cartridges which was intercepted at a UK airport en route to the US in 2010, where it was timed to detonate over the east coast.
Downing Street said there was an "evolving threat" and people should continue to fly but allow "appropriate time" to go through security.
American journalist Lisa Simeone, 57, said security staff at Heathrow were carrying out "vigorous" physical searches which she likened to assault, as well as extra tests for explosives.
The airport security blogger said men and women manning the scanners had adopted "invasive" methods akin to those in the US.
Speaking airside at the airport, Ms Simeone said there was a clear change in the tactics.
She said: "I saw one woman, she was white, being really badly treated. She was patted down twice and nearly lost her balance they were being so vigorous with her.
"There was also a lot of swabbing going on, people's belongings, their clothes and shoes, they even swabbed a baby's pushchair. It was so unnecessary.
"People were being checked for iPhones and things like that, but the biggest difference was in the physical checking of people's bodies."
A British aviation security expert, Philip Baum, said heightened security would mean longer queues and increased waiting times to board flights at UK airports.
"It will mean an increase in the number of random searches, secondary searches and an increase in the number of passengers asked to remove shoes and possibly all passengers being asked to remove shoes if they’re going on certain flights," he said.
"It stands to reason that if we’re going to spend longer doing checks, people are going to have to spend longer waiting in line to board flights."