Following the Third Doctor's alternate regeneration on the planet Dust (PROSE: Interference - Book Two), the TARDIS, sensing that something was wrong, became aware that the Doctor had been infected with the Faction Paradox biodata virus, intended to corrupt him into a member of the Faction. To protect the Doctor, the TARDIS took the virus into itself, holding it in check even as the power requirements for doing so increased to the point where, following its near-destruction after it was caught in a dimensional rift leading to the dream realm of Avalon (PROSE: The Shadows of Avalon), it was forced to draw power from a universe-in-a-bottle created by I.M. Foreman that the Time Lords had hidden in the Time Vortex.
Following its destruction, the TARDIS spent around five thousand years drifting in the Vortex before it reformed above Gallifrey, now in the shape of a vast Gallifreyan flower of remembrance — a symbol of death — when viewed in four dimensions, being too vast to get a real sense of its appearance when viewed with eyes only from Gallifrey.
Its structure was composed entirely of bone, its interior dimensions mapped onto its exterior making it the same size inside and outside. This also caused it to become a nexus point, affecting past and future events along the causal pathways, generating temporal anomalies in the resulting temporal pulses, the ripples focusing on luring the Doctor back to the ship. Its interior was filled with bone spiders — a relic of the true timeline that it was trying to preserve and restore (TV: Planet of the Spiders) — the Doctor noting that the corridors' topography resembled a web. One room of the Edifice featured the butterflies that the Doctor had kept in one room in his TARDIS, pinned to the walls and crumbling into dust. The Edifice's control room was also "inhabited" by the temporal "ghost" of the Third Doctor that should have existed before the Faction's interference, this avatar — created from the dust that had accumulated in the room over the centuries — allowing the Eighth Doctor to realise what had been done to him. Although potentially dangerous to those who entered it, the Edifice would respond to the Doctor's biodata, such as doors that had previously refused to open for others practically flying off their hinges to respond to him.
When Faction Paradox tried to take control of the Edifice — still unaware of its true nature — the Doctor pretended to have given in to the Paradox virus after being confronted with Grandfather Paradox, the version of the Doctor that would exist in the timeline where the virus infected him, exploiting the fact that the Grandfather was more in tune with the timeline created when history was changed rather than the original course of events that the TARDIS was trying to restore. As a result, he and Father Kreiner were sent to claim the Edifice, only for the Doctor to defeat the Faction agent that had been sent to the Edifice with him with the aid of the Third Doctor's ghost. However, they were subsequently ambushed by Grandfather Paradox, the Grandfather killing Krenier for his betrayal. The Third Doctor attempted to offer the Eighth three solutions to the current crisis, but was destroyed before he could suggest the alternative to simply running away or begging the Grandfather for mercy. As the Edifice's ancient weapons systems activated, the Doctor realised what the third option was; by removing the Edifice's dimensional stabilizer, the Doctor was then able to drain the Edifice's power by firing its weapons, causing its dimensional interface to collapse. The resulting power release destroyed Gallifrey, but also erased the Faction from history as the Doctor forced the universe to "choose" whether the timeline where he regenerated on Dust or Metebelis III was the "true" third regeneration. As a result of the power loss, the Edifice collapsed down into a small cube, which Compassion and Fitz left in the Doctor's pocket to regenerate while he stayed on Earth throughout the twentieth century, the ship regaining its usual police-box appearance by 2001. (PROSE: The Ancestor Cell, The Burning, Escape Velocity)