"The attack on the German embassy in Kabul and the latest Islamist videos threatening Germany make it clear that the terrorist threat has reached a new dimension," the government said in a statement on Sunday evening.
"Attacks in Afghanistan are increasingly targeting Germans. Germany is being named more and more in warnings published on the Internet. The latest threat explicitly warns Germany only," the Interior Ministry said.
Germany has about 3,300 soldiers in the relatively safe north of Afghanistan as part of NATO's 50,000-strong International Security Assistance Force (ISAF), but Berlin decided last year to increase its contingent to 4,500 troops.
The German government added that it believed the video of a presumed member of al Qaida made public late on Saturday by the SITE Intelligence Group, a US organisation that monitors Islamist websites, was "authentic."
In the 30-minute video message, a man calling himself Abu Talha Al-Alamani said the Germans were "gullible and naive" if they thought they could "escape unscathed when they are the third occupation force in Afghanistan."
"Letting me blow myself up in the name of Allah has been my wish since 1993," said the man whose face was hidden, adding: "Time is running out for the Germans. I say to the German people 'arise and become just again'."
SITE said the video, in German with Arabic subtitles, had been produced by
al Qaida's production unit As-Sahab and was dated October 2008.
"It shows that Germany has moved into special focus for al Qaida," Berlin said. "The man speaking (in the video) left Germany in the first half of 2007. We believe that he then went to a training camp in the Pakistan-Afghan border area ... We also believe he is in contact with leading members of al Qaida."
In November a video was released with al Qaida chief Osama bin Laden calling on all foreign troops to leave Afghanistan - and for the first time a version of the tape was released with German subtitles.
Saturday's suicide bomb outside the German embassy in the Afghan capital killed two Afghans and wounded US and German nationals. A spokesman for the Taliban claimed responsibility, saying the target was two German embassy vehicles.
Chancellor Angela Merkel was "horrified" by what she called "a terrorist act committed in contempt of human life", while stressing that Germany "would continue to maintain its commitment in Afghanistan", her office said.
Germany, which opposed the 2003 US-led invasion of Iraq, has beefed up security and surveillance in response to the threat of attacks by Islamic extremists.
The closest Germany came to an attack was in July 2006, when suitcases containing homemade bombs were placed on two regional trains passing through Cologne's busy main train station. They failed to detonate. The September 11, 2001 terror strikes on the United States were planned by an al Qaida cell in the northern German city of Hamburg led by Mohammed Atta, one of the hijackers of the planes involved in the attacks.
In September 2007 three men - two German converts to Islam and a Turkish citizen - were arrested in Germany on suspicion of plotting attacks against US citizens and interests. They were allegedly 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.