At a German concentration camp in occupied Poland during 1944, young Erik Lensherr is separated from his parents by Nazi guards. The child's desperate mind remarkably bends a metal gate until a guard knocks Lensherr unconscious (a recreation of the opening scene of the first X-Men movie). Scientist Sebastian Shaw, who has observed this incident through a window, calls Lensherr up to see him. Placing a metal coin on a desk, he orders Lensherr to use his power to move it. When Lensherr cannot, despite his best efforts, Shaw shoots and kills Lensherr's mother in front of him. In his rage, Lensherr's out-of-control magnetic power kills the two guards and destroys two rooms, to Shaw's delight. Shaw tells Lensherr that they will "have fun" developing the boy's power.
Around this same time, in a Westchester County, New York, mansion, young Charles Xavier is awoken when he thinks he hears a burglar break in. He heads down to the kitchen and finds a young, shape-shifting girl named Raven Darkhölme, disguised as his mother, who is looking through the fridge for food. Using his mind to talk to Raven, Xavier accuses his "mother" of being an imposter, and asks what it has done with his real mother, as she would not make him a sandwich or hot chocolate. Raven shifts back to her normal, blue-skinned form. Overjoyed to meet someone else "different" like him, Xavier invites her in.
In 1962, Lensherr goes to Switzerland and forces a banker (by ripping out one of the metal fillings in his mouth) to trace a bar of Nazi gold to Shaw's address in Argentina. In a tavern there patronized by former German soldiers, Lensherr kills three men as he learns that Shaw owns a yacht in Florida. Meanwhile, in England, Xavier has graduated from Oxford and is publishing his thesis on mutation; Raven is now his foster sister and works as a waitress. Simultaneously in Las Vegas, Nevada, CIA agent Moira MacTaggart follows U.S. Army Colonel Hendry into the Hellfire Club, where she sees Shaw, Emma Frost, Riptide and Azazel. Shaw calmly threatens Hendry, telling him that the Colonel should reverse his position on advocating that the U.S. install nuclear missiles in Turkey, a move the government had previously avoided so as not to provoke war with the Soviet Union. When Hendry refuses, Shaw has Riptide demonstrate his power to conjure tornadoes from thin air and hurls Hendry into a wall. Convinced, Shaw has Azazel teleport Hendry to the President's War Room, where he supports the missile placement in Turkey.
Shaw later meets with Colonel Hendry on his yacht, and refuses to give Hendry his money, at which point Hendry pulls out a grenade and threatens to pull the pin and kill himself and everyone on the boat's deck. Shaw takes the grenade and pulls the pin himself, and absorbs the blast -- Shaw is a mutant, and absorbs energy, which also keeps him young, then taps Hendry, expelling the grenade's energy into the Colonel, destroying him.
MacTaggart seeks Xavier's advice on mutation, and takes Xavier and Raven to the CIA to convince the chief that Shaw is a threat. After convincing them that mutants exist, they are to be taken to a covert facility, but first Xavier insists they track down Shaw. Shaw is aboard his yacht relaxing with Frost and Riptide when Lensherr appears. Frost uses her telepathy to pacify Erik and pushes him overboard.
Lensherr attacks Shaw, using the anchors and chains of the yacht to tear the boat apart. When Shaw escapes in a submarine hidden below the upper decks of the boat, Lensherr tries to stop him, his ability to control metal pulling him along in the water. Xavier stops him so that he does not drown, speaking to him telepathically and telling him it's useless to follow Shaw. Lensherr joins Xavier and Raven at the CIA facility, where they meet Hank McCoy, another mutant that Xavier accidentally outs. McCoy and Xavier use a prototype Cerebro to locate mutants and recruit several of them to train to stop Shaw. During the recruiting process, we also see Xavier and Lensherr trying to talk to Logan (Wolverine) in a bar. He promptly tells them to go to hell, and they walk off.
Shaw plans to meet with a Russian general, but sends Frost instead, who is then captured by Xavier and Lensherr. Lensherr tortures her briefly and Xavier taps into Frost's mind and finds out that Shaw plans to start a nuclear war between the US and Russia in order to wipe out all normal humans. Back in the US, the CIA facility is attacked by Azazel, Riptide and Shaw, who kill all the guards and agents present. Shaw offers the new mutants to a place on his side, but most of them refuse. He recruits Angel and kills Darwin by forcing him to ingest a massive amount of energy when he tries to fight back. When Lensherr and Xavier return they all go to Xavier's mansion and begin to train, though Raven is conflicted about hiding her natural form. Hank creates a vaccine that is supposed to turn his and Raven's appearance normal, however, when Hank takes it there are unexpected side effects: his mutant physical features are enhanced; he now has blue skin, blue fur and is several times stronger. The newly assembled X-Men team boards a specialized SR-71 Blackbird jet modified by Hank and fly out to the Caribbean.
President Kennedy institutes a blockade of a Russian fleet in the Caribbean Sea. Shaw travels with the Russian fleet to ensure that the missiles get to Cuba. Xavier, MacTaggart and Lensherr fly to the blockade to stop the fleets from engaging. Wearing a special helmet given him by the Soviets that blocks out telepathic interference, Shaw uses the sub's nuclear core to charge himself up. While Azazel kills the crew of the Russian missile ship, Xavier uses his powers to make a Russian officer on one of the escort ships fire a missile and destroy the cargo ship carrying the Soviet weapons before it crosses the demarcation line established by the United States.
With Xavier's help, Lensherr pulls Shaw's submarine from the water, but an attack by Riptide forces the X-jet and submarine to crash on a nearby beach. Xavier desperately tries to locate Shaw with his telepathic ability but is unable while Shaw is in the reactor room of the sub and wears his helmet. Lensherr goes after Shaw and finds him in the sub's reactor room. The two battle furiously and the shielding around the chamber cracks, allowing Xavier to locate Shaw. Lensherr tries to overcome Shaw with the metal in the room but Shaw counters with his own telekinesis and pins Lensherr to the wall. Suddenly, Lensherr plucks Shaw's helmet from his head with a length of cable and Xavier is able to freeze Shaw in place. Lensherr puts on the helmet to block out Xavier's telepathy and admits that he agrees with everything Shaw believes about mutants and humans and how he never would have developed his power if Shaw hadn't forced him to. Eric, however, is still vengeful about Shaw's murder of his mother and kills Shaw by slowly forcing the coin that Shaw taunted him with as a child through his brain while Xavier screams, experiencing the act himself. Eric exits the wrecked submarine with Shaw's body and announces to his fellow mutants that the humans in both fleets are their real enemies and that the mutants should band together to fight them. Xavier pleads with Eric to end the campaign but he fails.
The two fleets fire their missiles and shells at the mutants on the beach, but Lensherr, now fully in control of his abilities, stops the projectiles in mid-flight and then turns them on the fleet. In the ensuing fight Xavier manages to distract Lensherr, but when MacTaggart fires at Lensherr he deflects the bullets, with one striking Xavier in the lower spine. The missiles and shells all fall into the ocean or explode. Lensherr removes the bullet from Charles' back but, more furious than before, begins to choke MacTaggart with the chain holding her ID tags, blaming her for Xavier's injury. Xavier tells Erik that Moira is not the one responsible and Erik relents, realizing he injured his friend. Erik releases Moira, who rushes to Xavier's side.
Lensherr takes Raven, Angel, Riptide and Azazel and leaves, having convinced them that humans are their enemies. Xavier, now confined to a wheelchair for the rest of his life, and his fellow mutants return to the mansion, where he will open a school. He wipes MacTaggart's memory. MacTaggart reports to her superiors but has nothing to tell them, knowing that Charles had erased her memory of all recent events.
At CIA headquarters, Emma Frost sits alone in a specialized holding cell. The door is suddenly ripped from it's frame and Erik walks in, his new recruits waiting just outside. He is wearing a new uniform and a newer version of the helmet he'd stolen from Shaw. He tells Frost to call him "Magneto."