Sonic & Tails's Story is the second part of the Heroes Story in the Story. Sonic & Tails's Story must be completed in order to unlock the Challengers' Story. The opposite story is Mario & Luigi's Story.
When Sonic & Tails arrive in London, the night before the Opening Ceremony, Yellow Toad and Chao discover about the colored fog and flee away. Sonic and Tails finds Boo who tells them to run away. Sonic and Tails meet Imposters Mario & Luigi who challenge them to fight them.
After the Imposters are defeated, the Imposters disappear and Sonic and Tails wonder what is happening. Then they see Boo who tells them the truth about the fog about that it is taking athletes form.
After Boo flees to The Tower of London, King Boo meets Boo. Sonic and Tais follow them to the Tower of London. Boo tells King Boo what happened and that Sonic and Tails were the only people who survived the Fog. King Boo then finds out that have been behind him. Sonic & Tails challenge the Boos to a battle.
After the Boos are defeated, the Boos flee from the Tower of London as Sonic and Tails find the Fog Machine. Sonic & Tails destroy the Fog Machine and they head back to their room.