Germany crashed out of the World Cup at the group stage for the second time in succession despite a 4-2 win against Costa Rica on Thursday.
The four-time World Cup winners came into the match needing a win but were also relying on the result of Japan's game with Spain to progress.
But the Germans were eliminated from Group E due to goal difference as Japan followed up their defeat of Germany with another shock result by beating Spain 2-1.
"It is unbelievably bitter for us because our result would have been enough," forward Thomas Muller said. "It's a feeling of powerlessness."
Germany took an early lead but briefly fell behind in the second half as coach Hansi Flick made a flurry of changes, reacting to the live score of the Japan v Spain fixture.
The Germans started positively, with Flick's all-Bayern Munich front line turning the screws early, battering the Costa Rica defence before Serge Gnabry got his head to a curling cross from Leipzig defender David Raum after 10 minutes to open the scoring.
Midfielder Leon Goretzka almost doubled Germany's lead just five minutes later but his header was directly at Keylor Navas.
Complacency began to creep into Germany's game. Keysher Fuller, Costa Rica's goal-scoring hero in a 1-0 win against Japan, forced Manuel Neuer into a fingertip save after some half-hearted defending from Raum and Antonio Ruediger.
Flick moved Kimmich back to his familiar defensive midfield position at half-time, bringing on Lukas Klostermann at the expense of Goretzka, who like Kimmich started the match on a yellow.
Just seven minutes into the second half, word crept around the Al Bayt Stadium that Japan had scored two quick goals to take the lead against Spain, a result which would force Germany out of the tournament.
Flick reacted immediately, bringing on Niclas Fullkrug and taking off another midfielder in Ilkay Gundogan.
Germany appeared disjointed as Costa Rica went on the counter on the 58-minute mark, the ball rebounding off Neuer and into the path of Yeltsin Tejeda, who slammed it home.
Flick continued to chase the game, making more changes but it was Costa Rica who scored next when Juan Pablo Vargas tapped a free kick past Neuer to put his side past Spain and into the Round of 16. The goal was later recorded as an own goal.
Germany hit back minutes later through Chelsea forward Kai Havertz to draw level.
Havertz scored again in the 86th minute and Fullkrug added another in the 89th minute to bring the score to 4-2, but the side's focus remained nervously fixed on the group's parallel fixture.
The night ended with Germany losing out to second-placed Spain as Japan unexpectedly won the group.
It means Germany, who had not missed out on the knockout stages of a World Cup for 80 years until the 2018 tournament in Russia, have now been bundled out in the group stage for the second World Cup in a row.