Set in fifth-century Edessa during the time of Bishop Rabbula, the History of the Great Deeds of Bishop Paul of Qentos and Priest John of Edessa narrates the wonders experienced and performed by two holy men during a pilgrimage to Mount Sinai.

Desiring to lead an ascetic life and to serve the priesthood in anonymity, Paul abandons his bishopric in Italy and—like Alexius, the “Man of God”—travels to Edessa. There, he meets John. Not knowing a trade, Paul earns a meager living as a day laborer, but gives most of his money to the poor and prays everyday in the caves and mountains near the city. John realizes that Paul is a wonderworker, and so he begs to accompany him on his travels. Soon, the two friends leave Edessa to visit the monks on Sinai, but instead of reaching the site of their intended pilgrimage they are abducted and taken to Yemen by tree-worshipping Arabs. After a battle with a tree-god, they succeed in converting the Arabs to Christianity. During the long journey home, they encounter some unusual ascetics: a dendrite living in a mountaintop tree; and a band of wandering monks among whom is a woman disguised as a man.