When I was a kid in the days of the original Street Fighter II, the plots in fighting games consisted of the instruction manual, the before battle/after battle one-liners, and a single picture at the end of the game -- if that. Even then I wished for meatier plots in fighters; and over the years my wish has been granted.
Rival Schools/Project Justice
Rival Schools and its sequel Project Justice are the story of a secret brainwashing conspiracy permeating Japan's top high schools. Thus it follows several groups of students from these schools hunting for answers about who is behind it all -- and, more often than not, battling students and teachers from other schools to get those answers.
With its huge and varied cast, the students in each team are involved for their own reasons -- be that searching for a missing brother or just looking for a good fight. Moreover, losing battles does not always equal a game over. Rather, the story often changes to reflect your loss in drastic ways. Winning in certain ways -- i.e., via triple tech -- can also alter the story. This makes for an interesting dynamic plot with a lot of replay value.
Tech Romancer is a love letter to mecha anime in the form of a fighting game. In the future, the once peaceful Earth has been invaded by an alien tyrant. The only ones capable of stopping him are a group of unlikely heroes, each with his or her own unique giant mecha (that resemble many of the most popular anime mecha of all time).
Each character has his or her own story and, like Rival Schools, how you win battles can alter how the story unfolds. But best of all, the whole game is set up like you are watching an anime -- complete with episode title screens and commercial break "eyecatch pictures" in addition to the voiced conversation scenes that take place before and after each battle.
BlazBlue is a futuristic fantasy following the world's most famous terrorist, Ragna the Bloodedge, as he wages his one-man war against the government. He finds himself hunted by government agents, bounty hunters, and mysterious puppet masters -- all set on killing him, helping him, or simply stealing the awesome power hidden within his hand.
Each character in the game has his or her own story that can take a few hours a piece to fully complete. Moreover, each character's story has multiple endings based on your choices in the visual novel sections and on if/how you win or lose certain battles.
Persona 4 Arena/Persona 4 Arena Ultimax
Persona 4 Arena and Persona 4 Arena Ultimax are sequels instead of their own self-contained stories in an original world. In fact, they serve as sequels to both Persona 3 and 4 as they draw the characters from those games into a single new adventure. The story follows both sets of characters as they are drawn into the TV world of Persona 4 and forced to fight their friends for mysterious reasons.
While Arena has a version of the story for each character (one which tends to contradict the other characters' versions of the story), Ultimax trades that in for two common plots that switch between the characters to show their unique roles as the story unfolds. The big difference between the two versions of the story is who the main heroes are, the Persona 3 cast or the Persona 4 cast.
Melty Blood is a sequel to Tsukihime (and thus a spin-off of the vast majority of TYPE-MOON games). It follows a boy as he investigates accounts of a vampire serial killer in his town. Oddly, eye-witness descriptions of the killer don't match nor have the victims' bodies been found -- so it appears this may all be nothing but mere rumour. However, when he meets another person on the same mission, he learns that things may in fact be far worse than he originally feared.
This game has two main stories -- one for each of the two main characters -- with multiple endings for each. How you progress is dependent on whether you win or lose your fights and on how many rounds it takes you to do that.
Guilty Gear is another futuristic fantasy tale. After a century-long war between humans and the living weapons they created called "Gears," an uneasy peace exists until the day one of the remaining Gears sets off on a mission to free the imprisoned Gear leader. To combat this threat, the United Nations organizes a fighting tournament to gather the world's strongest fighters in one place and then pit the strongest among them against the rogue Gear.
While the first game has only a bare bones story mode, starting with the enhanced version of the second game -- Guilty Gear X Plus -- the series gained a more robust story much like the other games on this list. In this series, there tends to be two or three different routes per character. Which ending you get is dependent upon your use of "continues" and whether you win or lose certain battles.