North Rhine-Westphalian state police spokesman Frank Scheulen said contrary to earlier reports, the plane bound for Amsterdam was not stormed by commandos just before 7 am.
"Two men were taken into custody by police just prior to its departure," he said. "The are suspected of wanting to carry out acts of terrorism."
Scheulen said a 23-year-old Somali and a 24-year-old German citizen of Somali origin were arrested.
He confirmed reports that the two men had left notes in their apartments saying they were prepared to die in "holy war" and that they had been under police surveillance for several months.
But Scheulen said the arrests had been "nothing spectacular" and a KLM spokeswoman said that "this was not an attack" on this particular flight.
"The (two) passengers were asked to get off the plane, there was a baggage inspection and then when everything had been removed a full check of the cabin took place," KLM spokeswoman Ellen van Ginkel told AFP in Amsterdam.
The jet then took off and continued its journey as normal, she said.
The Berlin daily Tagesspiegel cited unnamed security sources as saying the two men - named by the paper as Abdirazak B. and Omar D. - wanted to fly from Amsterdam to Uganda and then to Pakistan to join the Islamic Jihad Union (IJU).
The IJU, a group with roots in Uzbekistan with ties to al Qaida, is believed to be behind the so-called Sauerland group of three men arrested in September 2007 on suspicion of plotting attacks against US citizens and interests in Germany.
German converts to Islam Daniel Schneider and Fritz Gelowicz and Turkish citizen Adem Yilmaz had attended training camps in Pakistan in 2006 and were believed to belong to the IJU. The men were found with over 700 kilos (1,500 pounds) of hydrogen peroxide, the substance used in the 2005 attacks on London's transport system that killed 56 people. The chemicals had an explosive power equivalent to 550 kilos of TNT.
If confirmed that the two men arrested on Friday also had links to the IJU, it would be the latest in a string of police actions this month linked to the banned group.
On September 18 police arrested two men, one a 27-year-old German citizen of Afghan origin and the other a 27-year-old Turkish national, who prosecutors believe were recruited by Yilmaz.