The Church of El Elemia has 13 strategic points, similar to how Tenba has its own points, to go in help of any town or village that gets attacked. The story of the Church of El Elemia is much older, and goes far back than the story of the predecessor of Tenba, the [Sakura Store]. During the war that ended the Second Era, when the Right Wing of Horus fell into the Sea of Death, almost no one of the inhabitants of the Left Wing knew exactly what was happening. So they organized a group to investigate what happened in truth, and that was the start of the Church of El Elemia.
While they were investigating, they discovered a document, the Legends of El Elemia, that boasted about the glory of the past civilizations, which were far more peaceful and wealthy than the present world. And the key to these civilizations were described as a trio of goddesses that could create land, heal the people, and even shoot fire, just by singing. Furthermore, it even said that these goddesses actually existed. This made the people start the Church, whose goals gradually came to be Let us revive the Trio of Elemia.
It was theorized that on the top floors of the Tower, there was a land sustaining a very ancient an advanced civilization, and that if someone was able to reach that [Holy Land], Platina, the Trio of Elemia would revive. However, until 15 years ago, their truly simple minds didn't have any grounds for these theories, and their legends weren't based on true historical facts, so they didn't even know if the Goddesses actually existed or not. Then, Kyle Clancy, calling himself Falss, suddenly appeared before them.
He announced "I am an Apostle of Elemia", and performed before the people the fabled art of Harmonics, which multiplies the power of the Reyvateils. Furthermore, he even said that he knew the complete process for the revival of the Trio of Elemia. The church executives at the time invited him to the Church as a Saint, and gave him a very high position in the church ranks. Afterwards, Falss formed an special group for making reality the coming of the Trio of Elemia, and began carrying out the necessary tasks for that purpose.
The main two functions of the Church are Give to the people a land where they can be comfortable, and the Search for the Trio of Elemia. The Church asks for contributions that are more reasonable than the fees that Tenba demands, including the construction of a church in the town, as conditions for granting their protection in exchange, and their contracts are town/village-wide.
Basically, all the inhabitants of the town/village that sign the contract with the Church become members of it after the contract has been signed. However, to be able to compete with Tenba in the center of the Special Safety Zone where Nemo is located, they also support individual contracts, like Tenba does.
In regards to the Trio of Elemia, until Bishop Falss appeared, there weren't any concrete methods for making them descend. The only plans they had were the exploration of historic ruins, while taking back any artifacts they found for their posterior investigation, and it was quite popular to take the challenge of the Journey to the Holy Land of Platina. However, even if they could hardly slip through the Pheyna Gate and protect themselves against the great power of the Teru Tribe, the next part of the Tower, the Frozen Eye, wasn't anything but a dead end because of its sealed warp gate. And if they tried to approach to the Frozen Eye from the air, their airships would receive electrical discharges from the Blastline, and would always end crashing.
The Church is structured in two parts: the Priests, which have the Bishop as the highest rank, and the Holy Maidens, which is the rank that the Reyvateils have when they join. The Priests are divided in the following four ranks: Cardinals, High Priests, Oracles and Candidates, but only the High Priests and the Oracles will surely get assigned a Holy Maiden Reyvateil as their partner. The Bishop and the Cardinals aren't able of having a Reyvateil as a partner, so they don't have any choice but cancel their partnership with their Reyvateil once they ascend ranks. For example, Radolf used to have a Reyvateil partner called Fayma before he rose to the Cardinal rank.
As for the Reyvateils that join as Holy Maidens, they receive a one-month training after their entry, and are coupled with one Priest after a ceremony called the Baptism. Usually, the Reyvateil has the right to choose her partner from any Priest that is higher than the Candidate rank. However, there are some cases in which the Cardinal has to assign a partner for them, but given the respect for wishes of the Holy Maidens in the Church, is a very rare event that the Cardinal assigns a partner for one of the Reyvateils. However, for the extremely strong A-Class Reyvateils, the Cardinal will assign each one of them to a Priest that has Melding abilities befitting of their power.
In the case of the Candidates and the Holy Maidens, given that they have entrusted themselves completely to the Church, they almost never are able to return home. They basically have guaranteed a normal lifestyle, though their salaries aren't nowhere as high as the ones that the Tenba Corporation gives. In comparison to the High Risk-High Return that Tenba has, the Church has many restrictions, but allows to have a modest, yet stable lifestyle.
The Church uses this term to refer to the Reyvateils. In a more strict sense, only the Reyvateil that has obtained the Hymn Crystal Linker, which allows the Goddesses to descend into her, is called the Holy Maiden. The Reyvateils who are currently registered to the church are no more than Holy Maiden candidates.
Relationship with Mir
The Church worships the Legends of El Elemia. Essentially, they have always worshiped the Trio of Elemia, but because of the conspiracies that Bishop Falss was scheming, its Priests committed disgraceful actions.
However, the one that the people of the Third Era was actually worshiping was still Mir, and that is because she was considered the second coming of the Trio of Elemia, and she was even worshiped in the Temple of Elemia located in the Falcon's Claw. During the Second Era, Mir was the one that made the legends of the Trio of Elemia (which date back to the First Era) true, and she did all of that alone. Therefore, it's quite natural that the people were worshiping her before she turned into the cause of the great collapse of the Right Wing of Horus.