Belah'dia
Belah'dia was a nation formed shortly after the Calamity of Water. The people blamed the mages for the way the war ravaged the land to its very core. Magic became outlawed and the people began persecuting those who used magic against the masses. Fearing for their lives, the mages fled to the deserts of Thanalan and built a small community. Like everyone else, survival became the number one priority, but the magi never forgot their beginnings, and found a way to infuse their arcane practices in the worship of their goddess.
Beginnings
Following the Sixth Umbral Calamity, the people of Mhach were persecuted for the destruction caused by their Black Magic. Practicing any form of magic was outlawed, and the reserves of knowledge were burned or destroyed. The survivors fled to the far flung deserts of Thanalan to rebuild. This would come to be known as Belah'dia. With the world still thrown so far off balance, basic survival was all that mattered, and the mages of Belah'dia scrounged everything they could to see the next day. They never truly gave up on their craft, and cleverly hid the study and practice of Black Magic in the worship of their patron god Azeyma, preserving their way and ensuring their knowledge could be passed down to later generations.
The Age of Communion
Several centuries later, after the destruction from the flood had subsided, the land finally began showing signs of flourishing. Massive droves of people immigrated to Eorzea, filling the new city-states with life. Racial tensions began mounting and saw individual races gravitating towards specific city-states, with the Lalafell migrating to Belah'dia. Descendants of the Mhachi mages were also amongst those who made their way back to the city, strengthening its ties to its founders.
Over the following centuries, the city-states began growing steadily and seeking to expand their claim on surrounding lands. This led to territorial feuds as well as infighting within the cities. Lalafellian royalty feuding also led to a massive divide amongst the citizens. This eventually led to the division of the nation into two new city-states: Ul'dah and Sil'dih.