"There is sufficient evidence against the accused to show that he killed two US American soldiers perfidiously and for base motives on the afternoon of March 2, 2011," the federal prosecutor's office said in a statement.
Arid Uka was charged on Monday with two counts of murder and three counts of attempted murder for the shooting rampage after he allegedly stormed a US military bus parked at the airport.
Uka shot dead the two airmen and critically injured two others while shouting "Allahu Akhbar" ("God is Greatest"), according to prosecutors. One soldier later lost vision in an eye.
He then allegedly put his handgun to the head of a fifth serviceman but it jammed. Pursued by this serviceman, he fled into the terminal building where he was overpowered and arrested.
The shootings have been called the first Islamic extremist attack on German soil. In 1986, a bomb blamed on Libya in a West Berlin nightclub killed two US soldiers.
Prosecutors say Uka, originally from Muslim-majority Kosovo but living for years in Germany, succumbed to the influence of Islamist propaganda and aimed to avenge what he saw as atrocities by US troops in Afghanistan.
"The investigation showed that the accused wanted to kill the soldiers because they belonged to US forces under the ISAF mandate in Afghanistan," the statement said, referring to the NATO-led operation.
Prosecutors said Uka, whom they believe acted alone and had no ties to "terrorist organisations", had the night before the attack watched a jihadist video online depicting alleged rapes of Muslim women by foreign soldiers.
The morning of March 2, he allegedly took public transportation to Frankfurt Airport, one of Europe's busiest, carrying a pistol and a knife in a backpack and in another bag, a second knife and 22 rounds of ammunition.
When he saw two soldiers retrieve their gear from a luggage carousel, he followed them to a bus waiting for them outside, which eventually filled up with a total of 16 US soldiers.
Uka then allegedly asked a soldier for a cigarette and asked where they were to be deployed. When he heard the answer "Afghanistan," the suspect loaded his handgun, prosecutors allege. The soldiers were not armed at the time, authorities said.
Uka is accused of shooting a 25-year-old airman standing next to the bus in the back of the head, then boarding the bus and firing another bullet into the head of a 21-year-old soldier in the driver's seat.
Two other troops aged 21 and 25 were shot in the aisle of the bus, both of whom could be saved with emergency surgery.
Uka then allegedly took aim at point-blank range at the head of a 22-year-old soldier who was ducking between two rows of seats and pulled the trigger twice. But the pistol jammed.
He then fled the bus, chased by the 22-year-old, and was captured in the terminal by two federal police officers.
The attack has prompted calls for more comprehensive police monitoring of extremist websites.