There are multiple story-lines to the game. I'm doing Sonic's right now, so It may take a while to finish it
Chapter 1: Strange Metropolis
Sonic looks around to see what world he's in. All of a sudden, evil-looking creatures rise out of the sky. They are angels, but they are possessed. The tutorial begins. After that, Sonic begins to fight them off. After you make them die, Bayonetta will appear.
Chapter 1 Boss: Bayonetta
Bayonetta appears after Sonic fights the evil angels. She thinks that Sonic is a power-hungry, evil Lumen Sage, so she battles him.
Attack power: High
Defense power: Average
Weknesses: Homing Attack, Melee attacks
Rewards: Unlock Bayonetta's story
After Bayonetta is defeated, she'll fight along Sonic.
Chapter 2: The Unlikely Alliance