This is my version of their history
Ancient Lords of Baator
The following should be considered speculative rather than definitive. It's disappointing when mysteries are solved and explained, but it's fun to theorize about them.
The Law-Tainted
Everyone's darkest suspicions are true: the earliest of Baator's lords were yugoloths. They were among the Tainted Ones who fled the Heart of Darkness.
How exactly the yugoloth race infected themselves with the taint of alien concepts is unclear; it is almost certain they did it deliberately. There came a time, however, that the General of their race determined that the unclean elements had incubated themselves within yugoloth flesh long enough, and it was time to purge them and see what new creations could be made from what they had hosted.
In the beginning, the number of law-tainted yugoloth rulers was nine, three groups of three. The number of layers Baator would ultimately divide into was decided by them.
If they ever had names, they were abandoned in order to prevent the General from tracking them down, or using their names to use the Heart on their spirits from afar. Because they had no names, they called themselves after the nature of their contaminations.
Taint of Blood
Taint of Darkness
Taint of Fire
Taint of Oblivion
Taint of Stone
Taint of Ruin
Taint of Iron
Taint of Chill
Taint of Mire
Taint of Blood was in many ways the lowliest of the nine. The taint this yugoloth suffered was not just of law, but of mortality. His presence caused other immortals to age and die, while he himself grew progressively more withered over the centuries. The others held him in contempt, an impurity among impurities, believing it was only a matter of time before this gaunt, almost skeletal creature died as a mortal would.
If Taint of Blood was the lowest, Taint of Darkness was considered by all to be the mightiest. Its power was learned in the depths of the Three Glooms and in the darkest realms of Mungoth. It had the power to blind and distort the divinations of its opponents, and it was through the Taint of Darkness that the others made their escape. So it was that all bound themselves in fealty to Darkness' Taint.
Taint of Oblivion had the power to erase and manipulate memory. It claimed to be the creator, or one of the creators, of the River Styx. It was this yugoloth who stripped its fellows of their names.
Taint of Stone could raise or shatter mountains. It helped in the actual construction of the plane. Its sibling, Taint of Iron, created the first cities for the exiled Law-Tainted to dwell in with their experiments and slaves. Taint of Iron's rival was Taint of Ruin, who created balance in the plane by making desolation and waste wherever Taint of Iron had grown too ambitious. The chief ally of Taint of Ruin was Taint of Mire, who preferred swampy bogs in which to perform her experiments on aberrations and many-legged things.
Taint of Fire, who had apprenticed in the shaping of Gehenna, ignited the furnaces of infernal flame, while its rival Taint of Chill created landscapes of snow, ice, and ash.
It is believed that all nine of the Law-Tainted were killed by the generation that would succeed them. However, there are no records dating from this ancient beyond ancient time. It could be that all nine are still alive, manipulating the history of Baator from behind the scenes...
The Elder Baatorians
The Elders were not individuals. They were assemblages, collections of primal concepts drawn from the substance of the plane. They had no names. They were, in fact, older than words or light. They would not incorporate these concepts until much later, when it was far too late.
They can, however, be identified somewhat by their functions.
The Corrector of Errors
The Enslaver of Alien Elements
The Answerer of Questions
The Unveiler of Deceptions
The Eraser of Mistakes
The Deceiver of Enemies
The Builder of Habitations
The Preserver of Trophies
The Manipulator of Lesser Forms
The First Baatezu Lords
The origin of the baatezu is not known for certain. Of course, the yugoloths claim that it was they who engineered the first of that race, though they are reluctant to mention the Law-Tainted. Baatezu myths say they were created by the Lord of the Ninth to aid him in dividing the multiverse under his control. In the library of Demogorgon is a variation of the World Serpent myth that identifies the Lord of the Ninth as one of the aspects of that complex archetypal being. Certain myths even claim the baatezu descend from fallen archons or other celestial beings.
What is known is that the Elder Baatorians ruled the plane for eons uncounting, until a new variation of evil law - the baatezu - fulfilled its function by conquering and subjugating its predecessor. Since then the baatezu have been the unquestioned rulers of the Nine Hells, though it may be that they will not be the last aspect of Order to be able to make that claim.
The following are some of the oldest names - or sometimes only titles - we could uncover, but these are perhaps not truly the oldest.
There were nine.
Mastema of the Torments, the Black Scourge,.
The iron charioteer known as the Donn.
Ssillegmik the Absorber.
Pyrishatar the Dancer.
Tannivar of the Grim Book.
Kafkefoni the Earthsinger.
Sammaaoth, the Lie of Beauty
Qol'Malshalgi, Voice of the Hellfrost
Atar the Accursed, Lord of Light
These nine were made not only to lead their inferiors (who were also winged, though of more humanoid form) in battle against the ancient natives, but to transform the nine layers in accordance with their will - even to become the layers, in a sense. This they did, and as a consequence none of them can be killed until the layers they are associated with are also destroyed.
Despite this, only two of them are still active in the affairs of the multiverse, and only one still rules.
Mastema of the Torments was cut into pieces by fiends from the Abyss. Its blood runs in rivers. Its spine and ribs have grown cities.
The Iron Charioteer no longer remembers his nature, having been bound into a humanoid form by an ancient haglike creature. He calls himself Dispater, and this is the only identity he knows.
Ssillegmik has become one with the swamps. It continues to devour all things on its layer, sucking down even the capitol Minauros.
Pyrishatar the Dancer was seduced by Belial. Some say she was bound in the heart of the volcano the city of Abryimis was built around; some say she lives still, entranced, as a member of Belial's harem.
Tannivar's library was destroyed, covered in flood waters and forever forgotten. Tannivar lingered on, bent and sorrowful of his loss, until he was devoured by Levistus. Apparently he remains dormant in the innards of the frozen prince.
Kafkefoni used her voice to draw forth the stones of her realm to crush and destroy the cities of the Ancients. She continued to rule with fierceness and determination, but her fascination with the buried ruins of her foe prooved her undoing. She would call them up and try to learn from them, and eventually she unearthed something she couldn't handle. They say she remains underground, broken, in the posession of those she once defeated.
Sammaaoth, in his garden realm, collected beautiful things and corrupted them from within. Triel the Fallen became one of his pets, for a time.
Qol'Malshagi was stripped of his mind by the insectoid Rimmon. He became a mindless, undead bladestorm, full of ice and fury and signifying nothing. Eventually Mephistopheles would learn the secret of commanding it.
Atar pierced the darkness of the deepest layer with purest evil light, using illumination to cut Nessus into manageable chunks. With this light Atar ruled Nessus for millennia until Triel the Fallen made a deal with the asura Absalom, bringing forth endless flights of celestials in exchange for a legendary cache of stolen souls. Triel, calling himself Baalzebul, forced Atar to accept himself and Belial as co-rulers in a new triumvirate. After a time, Atar managed to gain sole control of his realm once again, but suddenly quit, leaving for parts unknown. In the ensuing conflict, an avatar of the Unholy itself, Asmodeus, gained the throne of all Baator, and thus it has remained.
The Emanations
It came to pass that the Unholy One desired to cleanse or disinfect the plane of its current inhabitants and introduce a new pathogen. To rewrite the plane.
The unholy created nine emanations of itself, long and serpentine with vast wings, to execute its will.
Sargantanaeon, the Fiery One, Ruler of Avernus
Gagh Shekelah, the Smith, Ruler of Dis
Rhotomagaeon, the Concealer, Ruler of Minauros
Kafkefoni, Fiery Hinderer, now a mere concubine of Belial's
Tanniver, the Blind Dragon, Gray Guardian of the Book of the Fifth
Tagariraeon, the Haggler, Ruler of Malbolge
Sammaeon, Guardian of the Garden of the Seventh
Nuraeon, the Wind of Hellfrost in the Eighth
Ataraeon, Lord of Light in the Ninth
Chashek, the Lord of Darkness
Procession of the Hierarchs
In the tumultuous early days before the coming of the Unifier, many layers changed hands.
Sargantanas, Lord of Avernus
Dispater, Lord of Dis
Amaimon, Lord of Minauros
Kakfkefoni, Lady of Phlegethos
Levistus, Lord of Stygia
Ronwe, Lady of Malbolge
Sammaeon, Lord of Maladomini
Baalphegor, Lady of Cania
Atar, Bright Lord of Nessus
Melchiresha, the Unholy
The Primordial Rebellion
Myths say a third of the archons fell. A triumvirate is created in Hell. There is the beginning of a schism between those created as baatezu and the fallen archons and their followers.
Zariel, Lady of the First
Dispater, Lord of the Second
Amaimon, Lord of the Third
Levistus, Lord of the Fourth and Fifth
Beherit, Lord of the Sixth
Gargauth, Lord of Seventh and Eighth
Atar, Bright Lord of Nessus
Triel, Lord of the Flies in Nessus
Belial, Dark Lord of Nessus
Melchiresha, the Unholy
A Failed Coup
The triumvirate doesn’t last long; a lord called Asmodeus takes control after only a few centuries. Beherit and Gargauth attempted to seize control of the Hells. In a possibly unrelated attack, Levistus attempted to steal control of Asmodeus' consort Bensozia. All were punished.
Zariel, Lady of the First
Dispater, Lord of the second
Mammon, Lord of the Third
Belial, Lord of the Fourth
Armaros, Lord of the Fifth
Nergal, Lord of the Sixth
Baalzebul, Lord of the Seventh
Rimmon, Lord of Cania
Asmodeus, Dark Lord of Nessus
Interlude
Politics as usual, stretching across eons. In a blow to the baatezu camp, Baalzebul drives Nergal out of Malbolge, replacing him with Baalzebul's own vassal Moloch. Mammon loses his seat to the deal-maker Azazel the Serpent, who renames himself Mammon. Mephistopheles storms down from Nessus to seize control of Cania. He proves himself to the baatezu camp by framing Armaros, the fallen archon ruler of the Fifth, for a crime he did not commit. Armaros is replaced with the baatezu noble Geryon.
Zariel, Lord of the First
Dispater, Lord of the Second
Mammon Minauros, Lord of the Third
Belial, Lord of the Fourth
Geryon, Lord of the Fifth
Moloch, Lord of the Sixth
Baalzebul, Lord of the Seventh
Mephistopheles, Lord of the Eighth
The Dark Lord of Nessus
The Reckoning
After Mephistopheles gained his throne, tension between him and Baalzebul grew greater and greater. The Hells firmly divided into two camps, and their cold war eventually flared into the Reckoning. Baator's political planescape changed again. Later on, Bel seized control of Avernus from his mistress Zariel and Baron Molikroth stages a coup in Cania.
Bel, Warlord of Avernus
Dispater, Archduke of Dis
Viscount Mammon of Minauros
Great Belial and Lady Fierana of Phlegethos
Levistus, Prince of Stygia
Malagard, Hag Countess of Malbolge
Triel, Slug Archduke of Maladomini
Molikroth, Baron of Cania
The Dark Lord of Nessus
The Present
This brings us to the present state of affairs, more or less. Molikroth has revealed himself to be Mephistopheles in disguise. Levistus has designs on his neighboring layers. The Hag Countess has been replaced by Glasya.
Bel, Warlord of Avernus
Dispater, Archduke of Dis
Viscount Mammon of Minauros
Great Belial and Lady Fierna of Phlegethos
Levistus, Prince of Stygia
Glasya, Archduchess of Malbolge
Baalzebul, Slug Archduke of Maladomini
Mephistopheles, Archduke of Cania
Asmodeus, the Dark Lord of Nessus