The basic storyline of Myth involves a war between the human civilization of the world and entities known as the Fallen Lords, a group of seven Warlord sorcerer-generals that arose to drag civilization into ruins. The game opens in the seventeenth year of the Province's war against the Fallen Lords, a war humanity is losing. The principal western cities, Scales, Covenant and Tyr, were razed during the war, and only the free cities of Madrigal, Willow and Tandem still stand against the Fallen Lords. The armies of the west, formed from humans, forest dwelling fir'Bolg and dwarven refugees are led by The Nine, a group of nine sorcerer-generals called Avatara. The known members of the Nine include the leader Alric (the former King of the Southern Provinces), Cu Roi, Rabican, Murgen and Maeldun. They've recently found a living severed head buried in the Barrier, which they believe can turn the tide of the war with the Fallen Lords. The Fallen Lords are six powerful wizards enslaved by Balor. The known ones include Soulblighter (Damas), The Deceiver (Myrdred), The Watcher (probably Bahl'al), and Shiver (Ravanna) - the names of the other two are not revealed in the series. Their leader is Balor, previously the hero Connacht, now the Leveler. The Head claims to be an ancient enemy of Balor's, and the Nine intend to use the intelligence it provides to their strategic advantage.
The Legion represents the elite within the armies of the west, and the gameplay centers around the actions of the Legion during the last year of the war.
The story begins in the village of Crow's Bridge, where a small detachment of the Legion has remained behind to guard a bridge at the request of the locals, who were fearing for their safety due to the ever increasing number of refugees from the south. After repulsing an attack on the town, they move on to the Town of Otter Ferry to meet the rest of The Legion where they prepare to cross the Meander. However, the Mayor of that town sought to betray them in the hopes that he would be spared once the Dark sacked Madrigal. After a small squad dealt with the traitorous human, the Legion moves south to flank the army of Shiver which is laying siege to the free city of Madrigal. With every major city in the Southern Provinces destroyed, the free city of Madrigal is the headquarters of the Nine, so its fall would effectively end the war. Before the main attack began, a small detachment heads to Shiver's basecamp in the ruined village of Comfort with the intention of drawing as much of her army away from the main batlle to even the odds. The Legion manages to score its first notable victory as they completely destroy Shiver and her whole armies with a pincer movement from both The Legion and the Madrigal garrison, saving Madrigal. On the first night of this battle, Shiver is unexpectedly slain in a Dream Duel with the Avatara Rabican, a victory owed to the advice of the Head (who alerted them about Shiver's exaggerated vanity, a point exploited by Rabican).
The Nine take advantage of this momentum and attempt to recover Total Codex, a book that contains the past, present and future within its pages, from the ruins of the historical city of Covenant. Rabican personally sends a small taskforce from The Legion into the ruined city in search of the Codex when the expidition they sent before went missing. The force manages to retreive the Codex from the ruins of Covenant's cathedral, which was where the first expidition made a last stand to deny the enemy the artifact. After doing so they flee the area and manage to find a few survivors from the expidition with Mauriac, an officer and prince regent of Covenant during Alric's childhood. After a brief rest, they learn that The Watcher had enetered Covenant, intent on getting the codex and razing anything in his way. Mauriac tells The Legion of a secret tunnel that was used to get Alric to safety when Covenant fell to Balor during the war. They manage to fight their way out of the ruined city and into the tunnel, evading The Watcher. Despite nearly being buried alive twice in the tunnel, being shaken unstable by The Watcher's rage on the surface, they manage to get to the ruins of the city of Scales, linking up with the Avatara Maeldun and his southern garrison and handed over the codex. They soon learn that the combined armies of the north are en route in an attempt to hold Seven Gates and Bagrada, the middle and southern passes of the Cloudspine mountain range respectively, against the army of The Deceiver, who is preparing to cross the range to replace Shiver's forces in the west. They need to only hold out for a few days, until snow covers the passes. First, though, they destroy a World Knot (a means of magical transport) behind their lines, which would have allowed The Deceiver to send his forces directly into their lines. They succeed, and though the army of The Watcher remains behind their lines, if they can keep The Deceiver at bay until winter, they will be able to turn and hunt him down. The Legion is soon sent to investigate the disapperance of scouts in Bagrada and they soon had to repel an attack force led by one of the Trow. They manage to repel the attack and heavy snowfall closed of the pass within two days. The dwarves then take the inititive to ambush a hundred souless who had been seperated from their masters.
Against all hope, the West had actually pushed the Fallen Lords back to the mountains. With the Watcher still within the province, The Legion prepares for a violent winter.
Around this time, the Avatara Alric is captured by The Deceiver while searching for a fabled suit of enchanted armor in The Barrier, on advice of The Head. His eastern army is annihilated. Alric realizes that he had been deliberately sent into a trap. However, the army of the west knows nothing of this. They send a small group of heroes east over the mountains in a balloon, and they are able to free Alric. During their escape, which became a thing of legend, Alric duels and kill Sinis, one of The Deceiver's shade.
During Alric's rescue, the Legion goes to Silvermines in search of the Arm of The Watcher, lost when Balor freed him from captivity. The Deceiver also has a force in Silvermines searching for the arm as well, for he and The Watcher were old enemies before Balor bound them to his will. The Watcher was generally acknowledged to be the second or third most powerful sorcerer in living memory, and when the city of Tyr fell twelve years before, He and The Deceiver fought a Dream Duel from which The Watcher barely survived. The Narrator thnks that their rivalry stretches much further then that.
They succeed in recovering the Arm and evading The Deceiver's forces, but suddenly the great volcano of Tharsis overlooking Seven Gates erupts, melting all the snow in the pass, allowing the forces of The Deceiver to cross the Cloudspine. At the same time, The Watcher surprises Rabican's army from behind and crushes it, seemingly slaying the Avatara and scattering survivors around the mountain range. After this, The Watcher's forces press forward and tear through the army of The Deceiver, moving east of the Cloudspine and away from the army of the Province. The Legion is purseued by enemy forces intent of taking The Watcher's arm from them and they make a stand on a nearby hilltop, fending off the undead and their Trow commander. Maeldun positions his army to retake the passes of Seven Gates in an attempt to close the pass to the Fallen Lords. In this he is successful, both holding the pass and managing to kill one of The Deceiver's shades, Scaripant, who was trapped by the rising waters. The seventeenth year of the war ends.
The following spring, the Avataras Cu Roi and Murgen take the rested and reinforced Legion over the Cloudspine and into Forest Heart in an attempt to regain the support of the Forest Giants, who mysteriously withdrew their support of the west thirteen years earlier, leading to the fall of the Southern Provinces. their mission is disrupted when Soulblighter himself appears with his army. The legion with the Forest Giants' aid manage to repel the undead. In a stunning surprise attack, Soulblighter's personally falls upon the Legion and he traps the Legion within the Tain, a magical artifact used by the hero Connacht a thousand years earlier to trap and exterminate the Myrkridia, a species that had nearly hunted humanity to extinction during the previous cycle. The Tain is small enough to hold in the hand, yet contains a pocket universe of limitless capacity. Trapped within, the Myrkridia cannibalized each other until the last of them starved to death. The Legion came across a skull platform 30 feet high and 100 feet across topped with a battle standard, evidence that the Myrkridia had indeed been in this place. Murgen and the few members of the legion he could find searches for a way to free the 4000 men trapped within, negotiating many of the Tain's lethal traps, forces of the dark imprisoned with them and the giant spiders that infested the tain. Murgen eventually finds the exit and shattered the Tain. Soulblighter flees, startled by the unexpected destruction of the powerful artifact, which occured only mere moments after he used the artifact of The Legion.
Cu Roi and Murgen, sadly, do not survive the destruction of the Tain and many of the Legion are lost as well. Messengers inform them that Maeldun has lost the important mountain pass of Bagrada (and was presumably killed in the process) and that The Deceiver has crossed the Cloudspine at the northern pass known as the Stair of Grief - though he is no more mentioned for the rest of the story. They also learn of a civil war erupting in the west as soldiers rise up unexpectedly in support of The Head as what is left of the Nine attempted to destroy it and as a result two Avatara were killed, leaving only three left. The war has taken a terrible turn for the worse with so many Avatara dying. However, the fate of Alric becomes known to the Legion as he joins them. A small group of Dwarves, led by Balin the Pathfinder, leaves the Legion at this point and sneaks into Myrgard via balloon and parachute in an attempt to slaughter as many of the occupying Ghôls as possible. This far east, they were the closest to their occupied homeland then any of their race had ever been since its fall. Impossibly, they are able to destroy the Ghôl Godhead during their attack, securing their place in legend and retaking their homeland, killing the thousands of Ghôls occupying the city.
At this point, Alric convinces the surviving members of the Legion to head north through the Dire Marsh towards the fortress of Balor. Their small force can do nothing to save Willow, Tandem, and Madrigral from the armies about to lay siege to them, but they could win a more important victory instead. During his captivity and interrogation, Alric has learned by chance that the Fallen all drew their power from Balor, a measure in which Balor insures their obediance to his will. If Balor were to fall, all of the armies of the Dark would collapse, leaving only the Fallen Lords themselves to contend with (it's strongly speculated that The Deceiver himself may have passed on Balor's secret to Alric). And so they move north. Upon entry into the Dire Marsh, a small band of soldiers invistigated the disappearence of a scouting party that hadn't returned. They found no one alive, as they expected, but were able to recover an enchanted bow from the scout leader before it fell into enemy hands. With The Watcher constantly ambushing them from the front and Soulblighter charging them from the rear, like they were racing to see who could destroy the Legion first, Alric performs a daring feint. The Legion's rearguard engages Soulblighter, holding him at the Gjol river while the rst of The Legion heads north to attack The Watcher. Using arrows tipped with bone fragments from his own lost Arm, the feint is a success and The Watcher is slain, turned to stone by the arrows and then shattered, scattering his army and clearing the way ahead. Soulblighter then mysteriously stops pursuing the Legion at this point.
As they pass out of the Dire Marsh, they approach the abandoned trow city of Rhi'Anon, the oldest city of the Trow's ancient civilisation, in which Balor's fortress is located. After securing a bridge within, the Legion passes into the city, Alric has now come to possession of one of the five legendary Eblis Stones, an extremely powerful magical artifact. The beserk who delivered it, having come all the way from Willow 1400 miles away, refuses to talk about events in the west, hinting on the terrible situation back home.
Alric orders the 2200 survivors of the Legion to attack the fortress of Balor in a suicidal feint. A half-million undead stand between them and the fortress. Alric then prepares to take 100 picked men through a World Knot to a spot directly on top of Balor's fortress. With Balor's forces distracted by the Legion's suicidal charge, Alric believes that this small force could sneak up on Balor and assassinate him. During the nights leading up to this moment, the great comet that had been growing brighter and brighter in the sky has become brighter than the moon and is visible by day. Many of The Legion took this as an ill omen. As he departs alone, Alric informs the Legion that Madrigal, the last city in the West, has fallen.
At sunrise, The Legion begins it's attack on the fortress and Alaric summons his force and they head towards the fortress from the opposite side.Alric then plants a Myrkridian battle standard, retrieved from within the Tain, outside the fortress in an attempt to draw out Balor. Alric believes that this will work because Balor trapped the Myrkridia within the Tain a thousand years earlier. The men, thinking that the hero Connacht had done this, ask Alric how could that be. Alric reveals to them a disturbing fact, that Balor and Connacht were two different names for the same person. The legendary hero of the Wind Age, King of Muirthemne and emperor of the Cath Bruig Empire has returned as the greatest evil of their world. One of Connacht's notable acts after he was reborn as Balor was to destroy the city of Muirthemne, laying waste to the Cath Bruig Empire, the greatest empire the world had ever known. And Alaric hopes that this old emnity would lure Balor out.
The plan works. Balor is drawn from his fortress, enraged at the sight of the Myrkridian battle standard. Alric takes the opportunity to strike at Balor. He and his force cut through Balor's bodygurads before immobilizing him with one of the Five Eblis Stones, leaving Balor vulnerable to the swords of the Legion. They manage to decapitate him, and plan to take his head to the Great Devoid, a bottomless pit created by the Ancient Callieach, an extinct race of powerful magic users. Only by doing this would Balor finally be destroyed. It is believed that by throwing Balor's head into the Great Devoid, the spirit of the Leveler itself would be destroyed, not merely its mortal form. The thirty survivors of the Legion, magically transported to the Great Devoid by Alric, are ambushed by Soulblighter as they carry the head toward the pit, but despite their losses they are successful. Balor is destroyed, and the Fallen are rendered powerless, the undead armies collapsing.
The fates of the Fallen Lords after Balors death are varied. Soulblighter flees the Great Devoid, having failed his master. The Deceiver is pursued to the Stair of Grief by the remnants of the armies of the west after his army suddenly collapses around him, and he is trapped inside the Dramus River, separated from his scepter, using all his magical power just to stay alive. The Dramus then froze solid around him, as the heat from the eruption of Tharsis faded, forming Angurvadal Glacier. The Deceiver would remain in this condition for more than sixty years. Balor, Shiver, The Watcher and The Deceiver had all been destroyed or imprisoned. Soulblighter had vanished in the form of a murder of crows, not to be seen again for six decades. The fate of the last two Fallen Lords was not known, though they never again raised their heads.
The fact that the Leveler did not return after these events, in spite of the fact that the world was due a thousand years of darkness, suggests that he had indeed been destroyed, and that the cycle had been broken. This would make Alric possibly the greatest hero of the Myth world. Although his feats are generally not as great as Connacht's, he was able to defeat the Leveler and end the cycle, something Connacht himself was powerless to stop.
Following the events of the game, the remains of the Legion limp home, they and other survivors of the war begin the long process of rebuilding their cities. Having reclaimed his throne, Alric is able to act as both King and Avatara and aided the people, allowing the cities of Scales, Covenant, Tyr, Madrigal, Tandem, and Willow to be rebuilt. The Province recovers, and the scars of war begin to heal. Ever after, in honour of the original Legion's sacrifice, the armies of the west are all known as Legions. The fir'Bolg returned to their forest homeland and the dwarves rebuilt Myrgard to its former glory. Sixty years pass, and the armies of the west are well-trained and large. The Legions constantly patrol the Province, vigilantly watching for the return of the undead and dealing with bandits and criminals as they do so. Alric remains King; his powers as an Avatara allow him to remain active, despite his advanced age.
However, this peace was not to last.