Judges said that Shepherd, 37, could be granted asylum if he could show that there was reason to believe the US might committed war crimes during his tour of duty.
But he would have to prove that he had no other way to avoid service that he believed might breach international law - something the judges found hard to believe.
"Mr Shepherd not only enlisted voluntarily in the armed forces at a time when they were already involved in the conflict in Iraq, but also re-enlisted after his first tour," the judges wrote on Thursday [emphasis in the original].
"It's not what we hoped for," Rudi Friedrich, a spokesman for German charity Connection e.V., which supports conscientious objectors, told The Local.
But Friedrich said there was still cause for hope in Shepherd's case, even if the legal odds were stacked against him.
The court said that "an armed intervention engaged upon on the basis of a resolution adopted by the Security Council guarantees, in principle, that no war crimes will be committed".
"That's something we've seen to be false in recent years in Iraq," Friedrich said, "from Guantanamo to the bombardment of towns where civilians were still living.
"There are documents that show the air war in 2007 and 2008 targeted civilian areas. Shepherd might have been asked to maintain those helicopters."
Even if Shepherd's legal team can't prove that he could have been involved in war crimes if he returned to Iraq - something Friedrich admits is fraught with "mights and may haves" - there is still the possibility they could convince the court he would face persecution at home.
But the CJEU found on Thursday that the threat of prison wasn't "so disproportionate or discriminatory as to amount to acts of persecution", as it was part of the normal military justice system.
He first applied for asylum in 2010, saying that he would face persecution in the USA because he might be punished with prison or socially ostracized for the crime of desertion.
After the Federal Office for Migration and Refugees denied his application, he applied to the Administrative Court in Munich, which asked the European court for advice.
The case will now return to Munich, where Shepherd and his supporters will battle on.
The ex-soldier has been fighting his case for seven years now, and hasn’t seen his family for a decade.
He said he is currently saving up so that they can travel to Europe to visit him.