The Caliphate is the term for the line of rulers that led the original settlers of Umayma for over 2,000 years. It is largely believed that the dissolution of the Caliphate and the institution of the Nasheenian monarchy was one of the major factors contributing to the war between Nasheen and Chenja.
The Caliph was initially a decendent of one of the powerful magicians who helped remake Umayma. There was already a loose government in place among the magicians when the advance party of First Families arrived (relations of the same families who ruled the moons) and later, when people began falling from the moons, and magicians were a natural choice of leader in the early days. The "Caliphate," then, was the entirety of the inhabited world in the early years of Umayma.
However, as the world became more habitable, the First Families began to want more power over the world that they believed they were contributing more than their share to in building. They were resentful that they could not simply continue the government they established before the mass exodus from the moons by the remaining populations there, who are thought to have "fallen" from the sky many centuries - perhaps many thousands of years - before they were expected. Many saw rule by the Families as more appropriate than rule by magicians, whose powers were both necessary and feared. The rule of the Caliphate was often contested during these two millenia, with the Families sometimes gaining the upper hand. Finally, the many years of tepid peace broke, and the Families overthrew the Caliph. When the country, then simply known as the "Ummah," broke apart, it fractured along existing divisions and borders. Those who had lived for a thousand years on the moon Chenya ("Grace of God") and those who had lived on Nashin ("the sweetness that attracts the heart") had lived informally apart since the world's birth. The revolution simply made it official, and there was a mass exodus of Chenjans into Nasheen and Nasheenians into Chenja.
Nashin, or Nasheen, was from then on ruled by a monarch chosen by the First Families' most powerful Family. Chenya, or Chenja, was soon ruled by a loose affiliation of mullahs, who gained more power and influence over time. What's not often recalled is that Nasheen and Chenja remained separate, mostly peaceful countries for nearly 100 years after the break before full-scale war finally occurred between them.
From God's War:
Chenjans and Nasheenians should have followed the same rulings of the same Prophet, but words, even the words of the prayer language, were open to interpretation, and when Nasheen had disbanded the Caliphate and instituted a monarchy, existing divisions in those interpretations had reached a violent head.