The game begins with a news report of a growing mutant menace. A young mutant with a forcefield defies the Russian military as seen two weeks ago and a super-strong mutant leads an uprising in the Far East and even attacks the authorities. Just recently, Alison Crestmere (Magma) has recently been identified as a mutant on the verge of discovering her powers and is being dragged away by a soldier of the Genetic Research and Security Organization (G.R.S.O.). Mystique disguises herself as a guard and knocks out that soldier as Blob comes into view. Wolverine witnesses the abduction and attacks Blob just as Alison's powers activate when she wanted the fighting to stop. Blob eventually seizes Alison and he and Mystique take off. After recovering and taking out a soldier, Wolverine chases Mystique and Blob to rescue Allison. Wolverine battles through Anti-Mutant troops and is attacked by Mystique (disguised as Cyclops), some Brotherhood grunts, Pyro, and Mystique again. Going through the tunnel, Wolverine teams up with Cyclops and catches up with Blob.
After defeating Blob, evading Brotherhood grunts, and safely escaping in the X-Men's jet, Alison is brought to the Xavier Institute where she can talk with the X-Men and students, and explore her powers. The X-Men continue to explore leads that might indicate why Mystique and the Brotherhood of Mutants are interested in Alison.
The X-Men then go to a H.A.A.R.P. (High Frequency Active Auroral Research Program) base and fight their way pass the guards until they run into Mystique (disguised as a lab technician) who unleashes Pyro on them. After a battle with several H.A.A.R.P. guards, the X-Men face off against Toad, who manages to slip info to Mystique about the Sentinels.
After flashbacks with Sentinels and the Juggernaut, the X-Men head into the sewers of New York City to save Gambit from the Morlocks. After fighting their way through, the X-Men encounter Marrow and Healer in the Morlock's Haven. After fighting more Morlocks, the X-Men fight and defeat Marrow and rescue Gambit.
Professor X contacts the X-Men and tells them that Mystique is preparing to lead a strike on the U.S.S. Arbiter. At the Arbiter, Blob attacks the ship, causing heavy damage, and the X-Men are forced to leave. While on the Arbiter, Mystique finds and releases Magneto from his prison.
Back in the Xavier Institute, Magma completes her training and learns about Wolverine's past through a flashback at the Weapon X facility.
The X-Men then head to Russia to find and help Colossus when they learn the Brotherhood are stealing weapons grade plutonium. After finding him, they fight some Acolyte Warriors and thwart the Brotherhood's plot. They learn that Colossus' sister, Illyana, is sick, so they take her to Muir Island.
At Muir Island, Magma talks with Dr. Moira MacTaggert and helps Forge to restart his computer so that a life-support system for Illyana can be activated.
At the X-Mansion, the X-Men learn that cloaked G.R.S.O. soldiers have infiltrated the facility. With the help of Jean Grey, they locate and defeat the soldiers. Jean Grey, Emma Frost, and Professor X then enter the Astral Plane, where they fight Shadow King and rescue Illyana. As they leave, Professor X is captured by the Shadow King.
Cyclops is given a message by his brother, Havok, to meet him at the Weapon X facility. Cyclops learns that Havok has joined the Brotherhood, and they fight until Wolverine breaks it up. After freeing some Morlocks from their holding cell, they tell the X-Men that Gen. William Kincaid, a staunch anti-mutant supporter, has restarted the Weapon X facility, and is rebuilding Sentinels.
After arriving back at the X-Mansion, Jean Grey mentions that Professor X has been captured. Magneto arrives to see Professor X. When the X-Men won't join his cause, Sentinels attack and capture Magneto.
The X-Men learn that Magneto has returned to Asteroid M, his base, and has asked mutants to go to "The Mount". Gambit believes that the Morlocks may have a connection to the Mount, so they return to the sewers. They learn that Marrow has taken Healer hostage and has sided with the Brotherhood. The X-Men fight the Morlocks and free Healer. They then meet Gateway, a mutant who takes them to the Mount. At the Mount, the X-Men face Sabretooth and Avalanche. They escape, and Avalanche destroys the portal to Asteroid M in the process.
Back at the X-Mansion, Beast finally repairs the Astral Gate that Cyclops and Wolverine took from the Weapon X facility so that the non-psychic X-Men can rescue Professor X. They recover the parts of Professor X's mind while fighting dark versions of Blob, Avalanche, and Pyro. When they find out that Professor X has been brainwashed, Professor X unleashes four enemies: Ultimate Predator, Champion of Rhodes, the Sun Goddess and the Chaos Lord. These four enemies have powers that mimic the powers of Wolverine, Colossus, Jean Grey and Cyclops. However, Shadow King disappears with Professor X.
The X-Men infiltrate a Sentinel facility in Europe. The X-Men learn from a lab technician that General Kincaid is behind this facility. After fighting multiple Sentinels, the X-Men find Gateway and a Morlock in a cage. Gateway creates a portal to NYC in order to get the 5 trapped Morlocks out of the facility. After the Morlocks are back in NYC, General Kincaid appears and taunts the X-Men.
The X-Men head to the Astral Plane to rescue Professor X, who then battles and defeats the Shadow King in a battle similar to a Greco-Roman colosseum fight.
The X-Men head to Asteroid M and fight their way through Acolyte soldiers to get to the control room where Magneto is. After fighting Magneto, Mystique, and Sabretooth, the X-Men save the people on the space station when the Sentinels attack. After freeing Havok, the X-Men fight General Kincaid who arrives in Master Mold. When the X-Men defeat Master Mold, Magma uses Magneto's Graviton device to steer the asteroid back into space. The war against mutants has been prevented, but now the X-Men must prepare for the coming of Apocalypse.