The first cathedral is said to gave been raised by Bishop Aetios (about 630), the first bishop of ancient Pachoras (Faras) to come down in history. The building was constructed most probably on top of earlier structures. It was a structure on the plan of a basilica with an apse between two sacristies at the eastern end and a narthex (vestibule) at the western one.
The cathedral was rebuilt in the office of Bishop Paulos in the 8th century (starting after 707). Stone blocks from earlier Egyptian pharaonic temples were used in its construction. Five aisles were created by rows of granite columns and additional rooms were added at the sides. The walls were covered with images of the Virgin Mary, Christ, the archangels and saints. In time representations of local church hierarchs started to appear among the saintly figures.
In the 10th century, the cathedral underwent reconstruction in the times of bishop Petros (972–999). The so-called Cathedral of Petros lost its wooden roofing in favor of brick vaulting and domes supported on massive piers built in place of the columns. The church, which ultimately took on the form of a cross inscribed in a square, became much more narrow and dark inside.
The northern aisle of the cathedral was a place intended for women by tradition. The men gathered in the southern aisle, while the nave was left free for the procession of priests that passed through it during the liturgy. Closing off the nave was a semicircular apse with a dais for the clergy. The altar stood in front of it. This part, the so-called presbytery protected by an altar screen, was intended only for the clergy, There were two sacristies, one on either side of the apse. The entrance to the church was through a vestibule (narthex). Another small vestibule with a separate entrance led to the aisle for women.
Many inscriptions in Greek, Old Nubian and Coptic were discovered on the walls of the cathedral next to the paintings. Some were legends describing the representations, others were prayers left by pilgrims visiting the church. The most valuable discovery, however, at least for historians, was a list of bishops of Pachoras with the dates of their spiritual office rendered in paint next to their names. The list, combined with the testimony of other documentary sources, gave the opportunity to calculate the offices of particular bishops and in consequence to determine when many of the murals were painted.