Sonic Heroes is split into five stories - Team Sonic, Team Dark, Team Rose, Team Chaotix, and Last Story.
After passing Seaside Hill and Ocean Palace, they confront Eggman in the Egg Hawk. The trio defeated it and move on to Grand Metropolis, a city under the control of Eggman. After getting through Power Plant, the team meet Team Rose. Amy demands that Sonic must marry her and the teams engage in a fight. Team Sonic beats them. After this, they enter Casino Park, with 24 hours remaining. They defeated a huge number of Eggman's robots and entered Rail Canyon, in which they only have until sunset.
After infiltrating Eggman's base, they defeated the Egg Albatross. After defeating it, they realize the Eggman they're after is a fake, placed to stall for time as the fleet of Eggman's battleships filled the skies. However, they don't notice Neo Metal Sonic copying their data. After getting through a jungle infested with frogs who can summon rain, they encounter Team Dark. The team was shocked to see Shadow alive, but Team Dark picks a fight with them since they are after Eggman, too. Team Sonic defeats them and advances to Hang Castle and Mystic Mansion. Once more, they destroy another army of Eggman's robots and head to the Egg Fleet. They board the Egg Fleet in which they destroy a couple of airships and head to the main fleet where they defeat Eggman in the Egg Emperor. After blowing up the rest of the fleets, Sonic thanks Tails and Knuckles for their help. Amy finds Sonic and he runs away while both Tails and Knuckles look on.
After clearing two levels, they beat Eggman in the Egg Hawk. They then enter Grand Metropolis and Power Plant where they encounter Team Chaotix. Rouge suspects them of getting in their way of "her" treasure while Team Chaotix accuse them of being assassins for Eggman. Team Dark defeats Team Chaotix and move on to Casino Park and Bingo Highway. They confront Eggman, who tells Shadow that he has no past to remember. Team Dark destroy an army of Eggman's robots and advance to Rail Canyon and Bullet Station, defeating Eggman in the Egg Albatross. However, it turns out to be a fake. Shadow is distraught after seeing a broken Shadow Android. They leave, not realizing that Neo Metal Sonic is copying the data of Shadow.
Next, they go through the Frog Forest and Lost Jungle, finding Team Sonic, who are shocked to see Shadow alive. Afterwards they entered and escaped from a haunted castle in two levels and beat another army of Eggman's robots. The team find themselves on the battleships in the Egg Fleet and got to Eggman in the armada's core. They then defeat Eggman in the Egg Emperor. They beat the fake Eggman and Rouge looks for the secret treasure, only to find numerous capsules filled with Shadow Androids. Omega tells her that the original Shadow must exist in order for the duplicates to do so before setting out to destroy Eggman's facilities. Rouge then tells Shadow that she'll return to stealing the Master Emerald since Knuckles is around the fortress, with Shadow responding that some things never change.
After making their way across the seaside, they beat Eggman in the Egg Hawk and then find Team Sonic in a city, with Amy wanting to marry Sonic and accuses him of taking Froggy and Chocola. After defeating Team Sonic, it appears that Sonic used the fight to make his escape and Team Rose continues in Casino Park and BINGO Highway. Next they beat numerous Eggman robots. Next at Rail Canyon, Big and Cheese suspect Froggy and Chocola are close, so Team Rose destroy an underground base, beating Eggman in the Egg Albatross. However, they realize that the doctor is a fake, Froggy and Chocola are presumed to be held captive somewhere else. Believing that Eggman has something to do with it, they head after him through the Frog Forest and Lost Jungle.
After getting through Lost Jungle, Team Rose encounter Team Chaotix. They accused them of kidnapping Chocola, which lead to a team battle. Team Rose wins and they search throughout a haunted castle in spite of their fears. They take out an army of Eggman's robots and find themselves on Eggman's Egg Fleet and defeat his Egg Emperor. However, he is a fake too and dissolves into Chocola and Froggy and they are reunited with Big and Cheese. They hear a voice saying "Chaos data has been copied." When Cream notices Sonic, she tells Amy, who immediately chases Sonic while Cream and Big laugh in joy for their friend.
First, they beat Eggman in the Egg Hawk. They then take down every one of Eggman's robots in Grand Metropolis. After that, they run into Team Dark, who wants to pick a fight with them because Rouge believes they were getting in their way. After defeating Team Dark, The Chaotix advances to the casino. Continuing on, they defeat various Eggman robots. In Eggman's base in the canyon, they defeated Eggman in the Egg Albatross. However, he is turned out to be a fake, while the client reveals he knows that. He sends them to the Frog Forest, while Charmy and Vector suspect something about their client's real identity.
In the forest, they meet Team Rose, who accuses them of kidnapping Chocola. Team Rose are defeated and Team Chaotix journey to a haunted castle, beating another army of Eggman's robots. The arrive to the Egg Fleet and defeat Eggman in the Egg Emperor, which was revealed to be another fake. The Chaotix head to a room to rescue their client who is none other than the real Dr. Eggman. The Chaotix express their outrage of this revelation, but Eggman made a promise that he will pay them as he conquers the world. Team Chaotix doesn't accept the offer and Charmy beats Eggman up for promising what he hasn't got.
In the next scene, Team Sonic, Team Dark, and Team Rose racing down towards the figure laughing diabolically. The figure is none other than Neo Metal Sonic. He takes out the metallic parts of the fortress to transform into a dragon-like form known as Metal Madness.
Eggman tells the teams that Metal Sonic has copied their data and used the power of Chaos to transform into this monster; he then hopes that the Chaos Emeralds are present with them. It appears the teams brought out the Emeralds with them all along. Eggman doubts the possibility of defeating Metal Madness even with the 7 Emeralds. Sonic wants to take on Metal Sonic, but the others decide that they want to help him. Shadow comes with the plan to buy Team Sonic some time to use the Chaos Emeralds. Sonic agrees and declares to show Metal Madness the "real super power of teamwork!".
Team Rose battles Metal Madness first. Second, Team Chaotix, and thirdly Team Dark. After this, Metal Madness transforms into Metal Overlord. This is the signal for Team Sonic to use the seven Chaos Emeralds to become Team Super Sonic and defeat Metal Overlord, returning Neo Metal Sonic to plain Metal Sonic. Metal Sonic asks why he can't defeat Sonic. Sonic replies that they're Sonic Heroes and then tells Metal Sonic that he's waiting for a rematch against him and runs off. Tails and Amy chase after him, and Metal Sonic shuts down and collapses. Knuckles chases Rouge for going after the Master Emerald, The Chaotix chase Eggman for their money, and Shadow and Omega hold up the defeated Metal Sonic and look at each other.
At the end, Team Sonic is seen running off to their next adventure.