L'histoire est dans la continuité des deux épisodes Sonic Adventure, mais la mécanique et la forme du jeu s'en éloignent, revenant à des niveaux thématisés qui s'enchainent et plus de linéarité comme ce fut le cas sur les premiers épisodes en 2D.
Dans Sonic Heroes, le joueur a le choix entre quatre histoires où, dans chacune d'entre elles, intervient une «team» composée de trois membres avec lesquels le joueur joue simultanément et entre lesquels il peut alterner en cours de niveau en fonction des aptitudes dont il a besoin: la Team Sonic (Sonic, Tails et Knuckles), la Team Dark (Shadow, Rouge et E-123 Oméga), la Team Rose (Amy, Cream et Big) et la Team Chaotix (Vector, Espio et Charmy).