The story mode involved random people all fighting to get their hands on the "Ehrgeiz", a magic knife/dagger/sword thingy that could make dreams come true, or something like that. It really was nothing more than an excuse to slap together a tournament style fighting game.
As for the FF7 character's story lines, they didn't have any. They were just thrown in as a experiment to see how well an FF-Fighter would catch on. I played this game like crazy back when it was new, but I never could pull off an Omnislash!
Great game, though, just that it has a strange combo method that differs from traditional fighters. Give a try.
OMG I LOVED this game. Incredible graphics for its era...I remember how good it looked and went WOOOW. I must have played story mode for MONTHS on end in that game. Kept attacking and killing stuff over and over again. I think I stopped when some other RPG came out Either way I gotta find it now~