Following the launch of the Sega Dreamcast back in 2000 (I believe?!), Namco released the awesome fighting game Soul Calibur. (The sequel to the underappreciated game Soul Edge)
Not only was this game phenominal demonstration in the use hand-to-hand weapon combat. It was also musical masterpiece, which only got better with every installment.
Every stage had its own piece that accented the character that it represented. Here are a few examples.
Cervantes, The Undead Pirate
Mitsurugi, The fearless Samurai
Ivy, The Cursed Noblewoman
Xiangua, Princess of destiny
The music literally takes you on a world trip, very much like the characters in the game, as they journey to find Soul Edge.
If your interested here are a few links to check out the rest of the games and their sountracks. I HIGHLY recommend that you play the games yourself to get a full immersion of the astounding quality while playing them.
For all the details about each game from the series (including music)
Site with many Youtube links of a summary of the series from Soul Edge to Soul Calibur V