The man, who is now guarding his privacy closely and does not want to be named, first saw the picture of himself in a news story on June 16.
The article was about Emrah E., a German of Turkish extraction associated with African terrorist group al-Shabab, who was being hunted by police in Kenya on suspicion of planning attacks in the East African country.
But the pictures printed alongside it, supposedly showing Emrah from two different angles, were in fact of two different men - Emrah E. and the unconnected man from Stuttgart, Die Welt newspaper reported on Thursday.
By this time the two pictures – handed out by the Kenyan police on June 13 - had been circulated around the world as a double portrait of Emrah E. through news agency AFP. It was printed and published online by several German newspapers, including Die Welt.
The police believed Emrah E. had travelled to Somalia from Pakistan in spring 2011, and may have entered Kenya in May this year. He has since been caught and deported back to Germany.
But the man who was not Emrah E. has never met his supposed doppelganger and says he has never travelled to Kenya or Somalia. And since the picture of him became public, he has been wrestling with another, more sinister, mystery - where did it come from, and how did it get into the hands of Kenyan security forces?
"I can't remember where or when the photo was taken," he told Die Welt. "It was definitely not taken with my consent."
One theory is that it was taken secretly by the German intelligence agency, the Verfassungsschutz, while keeping the man surveillance. But why? Few would consider the student a threat to national security.
He says none of his family have ever had connections with the terrorist scene, and though he considers himself a practising Muslim, he is certainly not a fundamentalist - in fact, he is married to a non-Muslim woman.
He has been to Saudi Arabia several times with his family, to take part in the "Umrah" pilgrimage, but that is not unusual - several hundred German Muslims take part in the so-called "minor pilgrimage" every year, the paper reported.
"It's a complete mystery to me why the secret service would follow or photograph me," he said. "I've never met Emrah E. and I don't have any terrorist friends."
It also remains unclear how the Kenyan police got the photo. Police forces routinely circulate photos in international investigations, and Die Welt reported that Germany's federal police, the BKA, did in fact pass on the photo of the real Emrah E. - but they deny accidentally passing on the second picture.
"According to our initial investigations, we did not pass on the photo," a BKA spokesman told the paper.
It is considered unlikely that Kenyan security forces got the photo themselves, which leaves open the possibility that the picture was taken by a third intelligence agency, possibly when the Stuttgart student was in Saudi Arabia.
One German security official told Die Welt anonymously, "Something went very wrong here."
Meanwhil the Stuttgart student says he has been slandered by the blunder. "I hope it is cleared up, and I expect an explanation," he said. But it remains unclear who could – or would – provide it.