Mario and Sonic receive the Tokyo '64, which Toad finds addressed to them, as a gift to commemorate the 2020 Olympic Games in Tokyo, unaware that it is in fact a trap devised by Bowser and Dr. Eggman, who are watching from nearby. Luigi also arrives, and Toad asks him for help. However, Bowser gets impatient waiting for them to activate the console, leading to him deciding to give them a surprise and make them turn it on. His sudden appearance startles Luigi into turning on the console, causing it to suck Mario, Sonic, Bowser, Dr. Eggman, and Toad into the machine, which transports them back in time to the Tokyo 1964 Olympic Games. Inside the console, Mario, Sonic, Bowser, Dr. Eggman, and Toad fall into a heavily pixelated version of Tokyo. To return to the real world, they must win gold medals in Olympic Events, so they compete in various events.
In the real world, Luigi carries the Tokyo '64 while searching for Tails, with Amy and Daisy eventually joining in the search. They eventually find Tails, who joins the group after hearing about Mario, Sonic, Bowser, Dr. Eggman, and Toad's situation. Bowser Jr. suddenly appears and takes away the Tokyo '64, refusing to give it back. He eventually finds Eggman Nega, who investigates the system and realizes it was created by Dr. Eggman. After Tails explains the situation, Eggman Nega refuses to return the system and leaves with Bowser Jr. to analyze it more to free Bowser and Dr. Eggman. The group eventually finds Eggman Nega and Bowser Jr., the former of whom has begun his analysis on the console. He eventually states that his analysis is mostly done, but he has not found a way to free the trapped characters. He recalls that Dr. Eggman said that gold medals would have a special effect inside the game; however, only gold medals inside the game would have that effect. The group visits various venues, with at least one character joining in at every one. Eggman Nega sends power-up items that work only on Bowser and Dr. Eggman inside the console, but an impatient Bowser Jr. randomly pushes buttons on it, causing the power-ups to scatter all around the pixelated land. Tails asks Bowser Jr. for the Tokyo '64 back, and the latter says he will give it back if the group beats him at the Olympic Stadium. There, Vector beats Bowser Jr., after which Eggman Nega finally gives the Tokyo '64 back to Tails. However, Tails notices that the system is running out of battery, while Mario, Sonic, Bowser, Dr. Eggman, and Toad notice the world flickering inside the system. Eggman Nega had created the Excitement Battery, which will never lose charge once fully filled up, to solve that problem. The group eventually gets the Excitement Battery and fully charges it with excitement and cheers from the audience at various venues. Inside the game, the five trapped characters have collected enough gold medals to return to the real world, but the game's battery runs out, causing the game environment to fade away and turn black and each of the five characters to fade away into a single pixel. Tails and Luigi quickly switch out the battery, resulting in the five pixels regaining their forms and the game world becoming colorful again. The five characters soon exit the console and return to the real world.
After the final chapter of Story Mode, Mario, Sonic, Bowser, Dr. Eggman, and Toad can freely enter and exit the Tokyo '64, meaning Mario and Sonic can rematch Bowser and Dr. Eggman in minigames and events. To return the five characters to the real world, the player must talk to Toad.