Before the Deluge, Caetia was a minor goddess; the Lady of Dolphins (as well as seals and whales, but mostly dolphins), her worship was reserved for sailors and voyagers, all those who sought protection as they crossed the salty waters. But as the ocean enveloped the world, the great lords of the waters became more important, and on the island of Palamara, the Temple of Caetia was erected, and her priestesses exalted her as a great justiciar, whose earthly representatives brought order to shark-filled waters. For many years, the priestesses ruled Palamara as a matriarchal theocracy, where the ocean brought great bounty and justice was swift, ready and blind. But utopia is naïve, and soon, pirates showed up at Palamara's shore, periodically raiding and looting the villages and the Temple.

During one such raid around two centuries ago, the Palamarian militia captured a pirate lieutenant, a man named Firus, and Caetia's judgement dictated he be 'returned to his fold'; fed to hungry sharks. Firus was dropped to the sharks, sheep's blood covering his body, but they refused to bite at his flesh. He was brought again before the priestesses, who, after much deliberation, decided that Caetia protected the pirate, and that she must have some plan for him in store. The High Priestess, Adalette, took him under her care, instructing him in the ways of Caetia, and he soon became ardently devoted to Her service. He decided that his mission in life was to defend Caetia's flock from the pirates he once called brother, and took charge of the militia which had failed so many times to protect Palamara. He instituted a rigorous training schedule, and many militiamen were found unsuitable to serve. Those that weren't were so captivated by the rigor of training that they had to be employed as fulltime fighters, employed directly by the Temple. Firus's training paid off, and his force was able to repel the onslaught of pirates, and Palamara began to prosper.

It was in that time that Adalette announced she was with child, and that Firus was the father. This was a great controversy, for priestesses were expected to remain celibate, but it was understood that Firus's warriors were the answer to any insurrection, and the reformed pirate and priestess married. Firus grew more and more powerful, and the matriarchy of Palamara faded away, giving way to the martial rule of a man who once besieged the island. His fighters were knighted by Adalette, and Firus was named Grandmaster of the new order of knights, the Order of Caetia.

The island had been home only to villages, so it came as a surprise that Grandmaster Firus announced that the fishing village which surrounded the Temple of Caetia, Vilayet, would become a new city, and the formal capital of Palamara. Vilayet, in the subsequent centuries, would become a great fortress, and the fortifications which began under Firus proved effective against pirate attack. The Knight's staunch defence against piracy proved an inspiration to foreign nobles and lords, and funds in the form of donation flooded in, which were put towards funding a navy, and reinvesting in estates and businesses worldwide. Putting the new navy to the use, Firus announced he would attack the pirate stronghold of Garabar, and while the attack was successful, the Grandmaster was killed in the attack. His and Adalette's son, now a man, attempted to seize control in Palamara, but Firus's second in command rose to power after the fleet had returned, and the Order's power was made resolute. Garabar was renamed Caetiopolis, and the wealth of the Order continued to grow.

Now, the Order of Caetia acts as a cosmopolitan force of justice and commerce, whose navy patrols the post-deluge world's troubled water, and whose estates and primitive banking system stimulate economies worldwide. In addition to Palamara and Caetiopolis, the Knights now own the southern island of Nogus and the eastern island of Yalit.