A living weapon created by the enigmatic Weapon Plus Program, the past of the man known as Fantomex is shrouded in mystery. Dipped into liquid time and injected with Micro-Sentinel machines, Fantomex was dubbed Weapon XIII by the Program. Fantomex was injured when the train carrying himself and Weapon XII crashed in the Channel Tunnel that links London and Paris. Freed from his pod, Fantomex fled to the Paris headquarters of the X-Corporation, the global mutant search and rescue organization founded by the telepathic Professor Charles Xavier. Seeking sanctuary, Professor X and Jean Grey - a member of the team of superhuman mutants known as the X-Men whom Xavier founded - repelled the French authorities and escaped with Fantomex to his mountain retreat in E.V.A., a mutant flying saucer possessed of a pure machine consciousness.
There, as he healed his wounds, Fantomex revealed to them the existence of the Weapon Plus Program. He offered to sell information on the Program only if Xavier and Grey would help him stop the threat posed by Weapon XII. When they arrived in the Tunnel, Fantomex proceeded to shoot many of those who had been possessed by Weapon XII, including X-Corporation member Darkstar. On reaching the train, Fantomex located Weapon XII's pod and activated a remote detonator, killing Weapon XII instantly. Discovering the second pod, Grey realized that Fantomex was, in fact, Weapon XIII but still allowed him to escape down the Tunnel to England.
Fantomex later encountered the feral X-Man Wolverine in a mutant slave trader camp in Afghanistan. Fantomex had stolen a list of names and addresses of some of the richest people in the world who were engaged in the mutant slave trade. Fantomex also found the young Afghani mutant named Dust unconscious after she had unwittingly slaughtered her captors. Turning her over to Wolverine, Fantomex teleported away, leaving the X-Man to deal with the encroaching mercenaries.
