First Appearance: X-Force (1st series) #25
Last Appearance: X-Men (2nd series) #43
Reconstructed as Providence: Cable/Deadpool #6
Introduction
At least twice before, Magneto had constructed his own orbital space station from scratch out of an asteroid, naming them both Asteroid M. However, the orbital station known as Avalon was actually a pre-existing station from the future called Graymalkin. Previously belonging to Cable, the station had been destroyed when SHIELD tried to claim it and pieces of it had rained down to Earth. Magneto evidently discovered at least one section the station and rebuilt it in his image.
Demise of Graymalkin
Coming from 2000 years in the future, Cable had arrived in the past with a space station, which he had named Graymalkin, after the address for Xavier’s School for Gifted Youngsters. Using advanced technology, the station was cloaked from modern sensors – until a fluke collision with a European space probe which released an electromagnetic pulse damaged the station’s cloak and alerted its location to SHIELD. [X-Force (1st series) #20] Interested in Cable’s technology, Nick Fury and GW Bridge led a 
SHIELD contingent to the station. X-Force learned of the station’s appearance as well and teleported to the station via Lila Cheney, attempting to repel the SHIELD troops. However, a combination of the EM pulse and the battle between X-Force and Fury’s SHIELD agents caused a malfunction in the Professor’s operating parameters, resulting in an imminent self-destruction sequence. The only person who could override the sequence was Cable, who had recently been lost in the timestream. [X-Force (1st series) #16] Unable to stop the destruction, Cannonball ordered several key components of the station to be jettisoned for salvage. The rest exploded in a ball of fire.
The Rise and Fall of Avalon
However, not all of the station was destroyed. Some time over the next few weeks, Magneto discovered at least a portion of the station. Using his own ingenuity, as well as Shi’ar technology he had obtained during his time with the X-Men, Magneto rebuilt the station into a fortress in the sky. Much like his intentions with the previous Asteroid M, Magneto intended Avalon – his new name for the station – to be a haven for mutants.
To communicate this intention, Magneto sent his newly acquired herald, the mutant known as Exodus, to the Earth to recruit citizens. Among his first choices were members of X-Force who had formerly been members of the New Mutants. Magneto and Exodus had decided that it would be justice to lure Xavier’s followers over to Magneto’s cause.
At first, the X-Forcers did not recognize the station, due to the additions of Magneto. However, Exodus was sure to bring it to their attention. Having not been invited himself, Cable – who had recently returned from the future – 
followed a signal from Cannonball’s costume to orbit, where he immediately recognized the station as being Graymalkin. Incensed that his former home was being used by a madman like Magneto, Cable intended to destroy the station, but not before retrieving the artificial intelligence called the Professor. Much to his pleasant surprise, he found the Professor’s program intact and downloaded it into his cybernetics. Unfortunately, before the self-destruct could be activated, Magneto arrived, nearly killing Cable by magnetically unraveling his cybernetic parts. Cable and X-Force were barely able to escape with their lives. [X-Force (1st series) #25]
Magneto next extended his invitation to Avalon to the Acolytes, who happily joined. Heartened by his swelling ranks of loyalists, Magneto was eager to win converts as well. With the recent death of Illyana Rasputin, the X-Men were in mourning and gathered with friends and allies at her funeral. Using this occasion to make a point, Magneto arrived with his Acolytes… and his new space station, which he lowered to just above
Alarmed at Magneto’s seemingly malevolent turn, as well as his acquisition of the monstrous Avalon station, the United Nations enacted a contingency plan called “the Magneto Protocols.” Upon the activation, a network of carefully positioned satellites generated a protective mesh of electro-magnetic fire, inside of which Magneto’s powers would theoretically not function. Considering this an act of war, Magneto generated a powerful electro-magnetic pulse, disrupting electrical power throughout the globe. In turn, the X-Men realized that only they could end the threat of Magneto, and set upon their own plan. Fortunately, Xavier and his handpicked squad of X-Men had some advantages on their side. First, Magneto had used Shi’ar technology to repair much of the station - technology with which Xavier was very familiar. Second, and more importantly, they had an inside ally - Quicksilver, who had only feigned loyalty to his father.
Using the Shi’ar technology of the station, Xavier used Avalon’s teleportation technology to transport themselves to the station - and then use the same technology to transport all of the Acolytes to escape pods, which were then jettisoned. With Magneto now alone, Xavier, his X-Men and Quicksilver attacked. However, Magneto was still too powerful – and enraged at being wounded by Wolverine’s claws, he did the unthinkable, magnetically removing the adamantium from the X-Man’s claws and skeleton. Incensed in turn by this, Xavier struck back viciously, attempting to wipe clean Magneto’s hatred, ego and nightmares. The process left Xavier’s physically spent, but it left Magneto in a mentally vegetative state. With Wolverine severely injured (possibly fatally) and the Avalon station badly damaged, the X-Men made their escape in a spacecraft, leaving Magneto behind in the care of Colossus. [X-Men (2nd series) #25]
With Magneto no longer capable of leading his own cause, leadership fell to Exodus, who rallied the Acolytes. Within months, it seems that most of the damage to Avalon was repaired. However, a new threat was imminent.
In recent weeks, reality had been severely altered by the time-traveling Legion, son of Xavier, who had inadvertently killed his father decades before the formation of the X-Men. This had given rise to a world ruled by mutants – an Age of Apocalypse. However, citizens of this altered reality, aided by Bishop, the only one who remembered the original timeline, worked to undo the divergence of the timeline and ultimately succeeded. One of four citizens of this reality to survive the restoration of the timeline was Holocaust, the son of Apocalypse.
When the timeline was restored, Exodus and his Acolytes found Holocaust floating in the airless void outside Avalon and brought him inside. However, when Holocaust regained consciousness, he saw Exodus as an enemy – since he had been so in the altered timeline. Believing himself to be held captive, Holocaust erupted in destruction, killing some of the Acolytes and crippling the station forever. [X-Men (2nd series) #42-43]
Though all of the remaining Acolytes escaped, for a long while the X-Men and Acolytes were unsure whether Magneto himself had survived. While Colossus had escaped with Magneto in an escape pod, upon arrival the former master of magnetism could not be found. Much later, the X-Men would learn that the former ally to Magneto known as Astra had taken Magneto for her own ends.
Reconstructions
Among these ends was the creation of a clone of Magneto, whom the X-Men eventually adopted as one of their own. Though they believed him to be a de-aged real deal, the clone was given the new name of Joseph and fought by their side. 
Considering himself possibly to be the real Magneto, Joseph wished to learn about his past as a would-be despot. Finding data in Xavier’s computer memory banks, he learned that a piece of Avalon fell in the Andes mountain range in South America and decided to investigate. There, Joseph discovered a group of Acolytes, who were searching for the same piece of Avalon. Along with the rest of their number, they were led by Exodus, who was attempting to reconstruct a portion of the downed space station in the Arctic, calling it New Avalon.
Joining the Acolytes in New Avalon, Joseph quickly learned that the eventual launch of the station would result in a fissure in the Arctic crust, which would lead to worldwide devastation. After a conflict with both Exodus and an anti-mutant group called Humanity’s Last Stand, Joseph convinced the Acolytes not to launch New Avalon. Instead, they should keep the concept of New Avalon in their hearts. [Magneto #1-4]
Just as the destruction of Graymalkin had given rise to the station of Avalon, the destruction of Avalon gave rise to something new. Years after having lost his space station while having been gone, Cable decided to rebuild it anew. At the time, Cable’s telepathic and telekinetic powers were at an all-time height, having been 
freed of his techno-organic virus. From around the globe, Cable retrieved pieces of Graymalkin and Avalon that had fallen to the Earth. From deep within the Pacific, the Australian Outback, Tierra del Fuego and elsewhere, Cable found every remaining fragment and reassembled them into a new facility he renamed Providence. Eventually settling as an island nation floating off of the coast of Tahiti, Cable intended it to be a place of refuge, where free thinkers could meet and a find way to improve the world.