The flying mutant Bloodhawk, which the X-Men Meanstreak and Krystalin helped rescue from the Synge Corporation, aided the X-Men as they fled from their base at Neuvo Sol, after a failed assassination attempt on Xi’an that left him in a cocoon state, thanks to his evolving mutant powers. Later, when the new head of the Synge Corporation, Lytton Synge, killed his own father and blamed it on Xi’an, the X-Men worked together to clear Xi’an’s name. Serpentina, a girl with the ability to stretch her own limbs, was killed in a battle over the cocooned body of Xi’an, at the hands of their former teammate, Junkpile. Xi’an woke up shortly afterwards and revealed that his mutant powers had evolved, giving him the ability to heal with one hand, as well as his former ability to destroy with his other hand. He turned on Junkpile and disabled him with his destroying hand, yet left him alive. After Serpentina’s funeral, Timothy made his final decision to stay with the team, and the X-Men were complete.
Meanstreak later left the team briefly after Bloodhawk and Timothy were rescued from the Theatre of Pain, and headed to New York out of concern for his friend, Jordan Boone. The rest of the team eventually caught up with him, despite Xi’an’s immediate disagreement with Meanstreak for leaving, and together they tracked Boone’s disappearance to the man-beast, Ravage. With Ravage’s help they traveled to Alchemax’s floating city, Valhalla, and discovered that Boone had been transformed into Loki, the Asgardian god of mischief. When they arrived they were forced to fight another one of the genetically engineered super heroes, Heimdall, who they defeated with the help of Loki. They later assisted in the evacuation of the human populace of Valhalla before 2099’s Spider-Man, Punisher, and Doctor Doom disabled the city.
The X-Men began to pick up underground broadcasts from a woman known as Mama Hurricane, whom Xi’an connected to a woman named Hurricane who had helped mutants escape the Great Purge of decades earlier, a time when humanity turned against mutants and executed them in droves. Xi’an also sent Krystalin away to meet with a man named Ten Eagles, a former teammate of Xi’an in his criminal days, and the rest of the team tracked down Mama Hurricane. They found that she was the same Hurricane from the Great Purge, but now she led a group of degens, genetically engineered humans, known as the Freakshow. But after the X-Men Metalhead was infected by the Freakshow’s Contagion, causing him to become fixed in his metal state despite Xi’an efforts, and he met a pregnant woman named Rosalinda whom he fell for, he quit the team to join Mama Hurricanes’ group when the X-Men left.
When the X-Men replied to a message from Krystalin, they tracked it to the Sangre de Cristo Mountains in New Mexico and found Krystalin and Ten Eagles hypnotized by the mutant Zhao, the leader of the third incarnation of the X-Men, since believed dead. They discovered that Zhao had used a synthesized, psycho-active amplifier to boost his failing powers, which drove him mad, and he killed his original X-Men, believing them to have turned against his purpose. He then genetically accelerated the growth of a set of mutants and patterned them after Xavier’s original students, leaving them physically unstable. But after a mental fight with Xi’an, in which Xi’an outlaw personality took over his body, the X-Men were able to incapacitate Zhao and freeze the remaining members of his X-Men to save them from genetic degradation.
With his old, selfish personality dominant, Xi’an left the X-Men and traveled to find a being known as the Driver and the mutant paradise Avalon that Mama Hurricane told him about. Timothy, having been mentally changed since being kidnapped himself by the Theatre of Pain, ran to join him in his pursuit. They both left to find Broken Haiku, another of Xi’an’s old partners. On the way they ran into La Lunatica, a former servant of the Theatre of Pain, who was on the run from the Theatre and its leader, Brimstone Love. After a confrontation, Lunatica joined up with Timothy and eventually brought him to Junkpile, whose help she had enlisted against Brimstone. Together they hunted down the Driver using Haiku’s information and found that the Driver had uploaded dozens of mutants’ personalities into a database to try and save them for when the world was ready for them. Brimstone Love attacked and in the resulting fight the Driver’s database was destroyed. Then, Xi’an accepted Brimstone’s offer to join the Theatre, which freed Lunatica from his revenge for the moment. She eventually joined the X-Men to be with Timothy, now called Skullfire.
Skullfire returned to the X-Men’s new headquarters in Zhao’s old base in the Sangre de Cristo Mountains and told them of Xi’an’s decision. He then took up the mantle of the leader of the X-Men. Meanwhile, Meanstreak left the group again to go after his friend Boone, who then called himself Halloween Jack, and together they overthrew the Synge Corporation and took over Las Vegas. Jack later started up a virtual unreality generator in Vegas, which Doom had to step in and contain, and Meanstreak and Krystalin, who followed him, again returned to the X-Men. In meantime, Cerebra had discovered how to fix the frozen members of Zhao’s X-Men, but Xi’an appeared and kidnapped them and the comatose Zhao, and returned to the Theatre of Pain.
Skullfire, Lunatica, and Cerebra set out to find Xi’an and bring down the Theatre of Pain. With information gained from Haiku, they disguised themselves as outcasts and entered the Floodgate, the gathering point for the Theatre of Pain’s victims. There they meet Quiver and Sham, fellow mutants, who helped them distract the Theatre long enough for Skullfire and Lunatica to fight with her former sisters, the Norns, and Cerebra to sneak in until she was captured by Xi’an, calling himself Controller X. Skullfire and Lunatica were also captured, and Skullfire was put in a refuse dump along with Junkpile, who was rebuilt and turned into a S.H.I.E.L.D. officer by the then-President Doom. They both broke out and joined up with the rest, along with Bloodhawk, Krystalin, and Meanstreak, who came after them. Together they fought Zhao’s unthawed X-Men and ended a broadcast of combined psionic suffering that Xi’an was orchestrating. And before Brimstone could stop them, Xi’an used Zhao’s body, which was acting as a psychic battery, and turned it on Brimstone in order to gain control of the Theatre. But Brimstone escaped, and in a fight with the X-Men, Lunatica used her psychic-vampire powers to snap Xi’an out of his megalomaniacal rampage. After Doom appeared and shut down the Theatre, the X-Men, along with Quiver, Sham, and a freshly repentant Xi’an, traveled to the newly created Halo City.
Halo City was built by Doom to act as a refuge for the Theatre's victims, with his Black Cabinet member, Morphine Somers, acting as governor. The X-Men became its guard, called the Protectorate. Xi’an began his repentance by healing anyone in need at the polyclinic, guarded by the Sisters of the Howling Commandments. Graverobber, a mutant with the ability to raise the dead, and his group, the Undead, later attacked the city. They demanded Zail Haddad, Shakti’s father, who endangered the Graverobber and countless others in medical experiments. The Undead eventually killed Skullfire, using a revived Serpentina as a distraction, and brought him back to threaten the city by destroying its power generator, the Spark. In an attempt to save the city and some captured X-Men, Morphine gave Zail up, but wired him with an explosive that put him in a coma and killed the Graverobber, releasing his hold on the Undead. Serpentina was reburied, and it was revealed that Skullfire was slowly transforming into a being of pure energy, and couldn’t really die.
Cerebra soon quit the group, being reassigned as the leader of the young mutant group, X-Nation, by Doom. After being contacted by Book, a mutant savant whose physical bulk made him incapable of movement, a group of the remaining X-Men broke into the Quetzacoatl Corporation and stole him from Javier Belize, the head of the corporation. Metalhead returned again, able once again to transform into any metal he chose, and brought along Rosalinda, who was due to give birth to a powerful mutant. Vulcann, a being that believed the boy to be a future messiah for mutantkind, soon attacked the X-Men and stole the boy, genetically accelerating his growth until he was an adult, named him Darkson, and turned him against the X-Men.
Then the planetoid arrived, orbiting the Earth, and caused the polar ice caps to melt, creating massive flooding across the planet. Halo City was soon flooded itself, and the X-Men rushed to save the denizens from the waters. The Atlanteans took advantage of the surface dwellers’ vulnerability and attacked, sending troops to Halo City. The X-Men became trapped on a single ship, sinking into the water, while Vulcann and his Darkson threatened them, and a giant Atlantean ship rose from the water to attack them. But Vulcann’s Darkson destroyed the ship and saved an armada of mutant refugees in the process. While he was distracted, Bloodhawk dropped Metalhead on Vulcann, and armed with an anchor from the Atlantean ship, Metalhead dragged his godson’s captor under the waters where he drowned. Then, before Darkson could turn on the X-Men, Skullfire appeared from another apparent physical death as an energy being and told Darkson the truth about Vulcann and his mother, then shocked him into unconscious with the power of the storm.
The X-Men were left safe aboard a ship, riding the waves of the floods. Except for Meanstreak, who previously left when he found himself sucked away by mysterious beings of light, the X-Men remained intact. And along with Nostromo, the last surviving member of the X-Nation team, and the child-like Darkson, they began their journey to the Savage Land, the last populated area on the planet.