One of the favourites for the gold medal, Spain, put in a terrible performance as they had Inigo Martinez sent off and lost 1-0 to Japan.
Spain should have lost by a lot more as their passing game deserted them and they went behind as Yuki Otsu arrived unmarked to meet a corner and give Japan an unlikely lead.
Then less than ten minutes later Martinez was given his marching orders for hauling down his man when through on goal and Spain were unable to get back into the game.
It was the first time the Japanese had ever beaten the World and European champions at any level.
Spain started the game by trying to impose their usual possession-based dominance on the game but they were hustled from the very first whistle by an energetic Japanese outfit.
Chelsea's Juan Mata forced Shuichi Gonda into a fine save with Spain's only serious effort of the first half but it was Japan who were threatening more regularly and they were rewarded after 33 minutes when Otsu outmuscled Martin Montoya to prod home Takahiro Ohgihara's corner.
Kiyotake should then have doubled the lead as he pounced on a wayward backpass from Alvaro Dominguez but after rounding David De Gea he just could not turn his shot on target from a narrow angle.
Spain were then plunged into even more trouble moments later when Martinez was sent-off for bringing down Nagai just outside the area. And despite half-time appearing to come at the right time for Luis Milla's men they looked just as rattled after the break as the Japanese passed up a host of opportunities to extend their lead early in the second half.
De Gea was called into action to make a fine save from Higashi in the 49th minute but the Manchester United goalkeeper should have been left helpless when Nagai broke through on goal moments later, only for the striker to pull his shot inches wide of the target.
Kiyotake had an almost identical opportunity two minutes later at the end of an amazing solo run through the Spanish defence but again his shot slipped just wide.
Milla had introduced midfielders Ander Herrera and Oriol Romeu for more offensive options in Isco and Adrian Lopez to try and stem the tide and while the tactic worked in preventing the Japanese counter-attacking with ease, Spain still struggled to create their own clear-cut openings.
Jordi Alba's effort was easily smothered by Gonda with 12 minutes remaining but Spain were again thankful to De Gea as he made a stunning stop to once again deny Nagai before Hotaru Yamaguchi sliced wide with the goal at his mercy in stoppage time.