The story of Soulcalibur Legends takes place between Soul Edge and Soulcalibur, and is based around Siegfried Schtauffen's transformation into Nightmare. The game begins as Siegfried finds Soul Edge on a ship. He battles Cervantes on the deck of the ship. Later, Siegfried is tasked by the Masked Emperor of the Holy Roman Empire to find the remaining pieces of Soul Edge in order to use it to win the war against Barbaros of the Ottoman Empire.
Series staples Nightmare and Cervantes make an appearance in the game as non-playable bosses. Assassin, Berserker and Lizardmen from Soulcalibur II also appear in the game as generic enemies.
Sultan Barbaros - Barbaros originally appears to be the main villain in Soulcalibur Legends. He was once the leader of a band of thieves when his band discovered Soulcalibur in the home of a general. Barbara, part of the same gang stated that Barbaros changed personality-wise when he claimed Soulcalibur. The spirit sword bestowed Barbaros with immense power, causing him to grow into a giant and allowed him to conquer the Ottoman Empire where he crowned himself sultan. He fought against the Holy Roman Empire, leading an army of Evils (monsters) to lay siege to the city of Vienna. The Masked Emperor enlisted the help of Siegfried to regain the shards of Soul Edge and combat Barbaros since Soul Edge was the only weapon that could stand up to Barbaros and Soulcalibur. After recovering all the shards Siegfried battled Barbaros and defeated him, causing Soulcalibur to emerge from his forehead.
Fanfir - After the Evil Seed event, Fafnir the dragon appears as a boss character in the game. Fafnir was the first dragon and that all the myths about dragons all over the world were inspired by him. He was slain by the hero Sigmund (whom Siegfried is named after) who slew the dragon using his sword Requiem. According to the legend, Sigmund asked his friend to reforge his broken sword, Gram, who gave his life for the sword. In his grief, Sigmund renamed the sword Requiem in honor of his friend and after defeating Fafnir he placed Requiem in an altar in the ancient Cathedral where Fafnir roosted. In the 16th century Fafnir is one of the Guardians that holds a shard of Soul Edge. The heroes need to enlist the aid of a scientist named Leonardo who claimed to have invented a weapon that could kill a dragon, which were needed because Fafnir could not be fought while in the air by conventional means. With these weapons Siegfried and Ivy are able to slay Fafnir and recover the shard. Later on Fafnir and the other guardians are revived by Soulcalibur but are slain once again by Siegfried.
Ilona Farkas - Iska Farkas' sister who got taken by Barbaros. Iska is always mumbling about Ilona and how he regrets not saving her. When Barbaros attacked Hungary, Iska fled but forgot Ilona. The Masked Emperor was made to look like her, revealed at the end of Soulcalibur Legends. Before his death, Iska starts to say something to her, but it is cut off. Their graves are shown at the credits, showing that Ilona did die or at least had a headstone dedicated to her.
Iska Farkas - He is one of the key characters in the game. Despite being initially presented as an ally, he is eventually revealed to be the main antagonist, having manipulated the characters into retrieving Soul Edge and Soul Calibur for his use. He is a refugee and Hungarian prince who serves as a court jester for a Masked Emperor. Iska has heterochromia with one blue eye and one red eye. His belts also correspond to this trait. He was born in Buda who lived with his sister Ilona until the usurper sultan, Barbaros, attacked the city and destroyed it, though his sister allowed him to escape with his life by sacrificing herself. Iska then went around the world looking for shelter, but all those that took him in eventually betrayed and used him, and then he studied under the famous alchemist Paracelsus who taught him much at Basel, until Iska disappeared, stealing Paracelsus's notes on the creation of false humans and was said to have made at least one successful artificial human. He thought up a crazed scheme to take over the world using the swords Soul Calibur and Soul Edge, to gain power for his lost sister. He used Paracelsus's notes to create a homunculus, made to look in the form of his sister. She managed to become the Masked Emperor of the Holy Roman Empire. He faked a story of being brought in by the "Masked Emperor" and becomes her court jester. His scheme comes into effect, as his homunculus has Siegfried and several other companions reluctantly agree to help the Holy Roman Empire against Barbaros of the Ottoman Empire (who wields Soul Calibur) by strengthening Soul Edge, which Siegfried wields. Iska is very persuasive in keeping his comrades to uphold their agreements and constantly reminisces about missing his sister and his home, lamenting his weakness, and wishes that he had strength and power which he did not have then to survive the pains of his life. After Soul Edge regains power and Siegfried kills Barbaros, claiming Soul Calibur, the "Masked Emperor" claims Soul Edge and tries to attack Siegfried and claim Soul Edge for Iska. However, a new version of the Evil Seed comes from Soul Calibur as the two swords clash, knocking Siegfried far away. Siegfried ends up sealing Soul Edge's power after realizing that he killed his own father at the peak of the Himalayas, however keeps it. He also gets Requiem here. The group storms Vienna to defeat the Emperor, and after Siegfried does, he plants Soul Edge into the ground alongside Soul Calibur. Iska then claims them (restoring Soul Edge's power using Soul Calibur), revealing his scheme to Siegfried. He then attempts to kill Siegfried, but Siegfried instead wins and Iska dies. During the credits there are two graves that say Iska Farkas and Ilona Farkas. Siegfried keeps Soul Edge, eventually succumbing to the Evil Seed and becoming Nightmare.
Soulcalibur Legends was released on November 20, 2007 in North America and was released in Japan on December 13, 2007. The game was eventually released in Europe, including the UK, on August 28, 2008.
A manga adaptation was published during the first year of the Japanese publication Kerokero Ace. The adaptation featured Siegfried, Iska and Ivy joining together on the main quest of the game. The adaptation's style was mostly comedic, including frequent 4-komas with running gags (such as Siegfried's annoyance that Ivy towered over him).