Das Pauluskloster liegt ganz in der Nähe des Antoniusklosters ebenfalls in den öden Bergen der Östlichen Wüste Ägyptens nördlich von Hurghada. Der ägyptische Name des Paulusklosters lautet Deir Mar Bolos.
Das Pauluskloster ist kleiner und noch schwieriger zu erreichen als das Antoniuskloster. Die Mauern des Paulusklosters wurden in und um die Höhle errichtet, in welcher der Eremit Paulus im 3. und 4. Jahrhundert etwa 90 Jahre lebte.
Paulus wurde in Alexandria als Sohn einer reichen Familie geboren. Als er mit sechzehn Jahren von den schrecklichen Christenverfolgungen durch die Römer erfuhr, beschloss er, ein Leben als Eremit zu führen. Abgestoßen vom Verhalten der Gesellschaft zog er in die Östliche Wüste und suchte sich eine Höhle, in der er fortan wohnte.
Die Pauluskirche wurde über der Höhle des Heiligen Paulus errichtet. Die Höhle des Heiligen Paulus gibt bei der Besichtigung einige Schätz preis. So stehen mehrere Altäre und Kandelaber im Inneren. Auch Ikonen sind zu finden und ein Sarkophag, von dem man glaubt, dass die sterblichen Überreste des Heiligen Paulus darin ruhen.
Als der Heilige Paulus verstarb, so erzählt man sich, soll sich der Heilige Antonius, damals selbst schon über 90 Jahre alt, auf den Weg zur dessen achtzig Kilometer entfernten Höhle aufgemacht haben, um ihn zu begraben. Obwohl das Pauluskloster in Luftlinie nur etwa 35 Kilometer entfernt ist, muss man durch die Berge mit ihren gewundenen Pfaden eine weit größere Distanz zurücklegen. Man kann übrigens auf dem gleichen Weg wie der Heilige Antonius zur Paulushöhle wandern, muss dann allerdings Campingausrüstung mitführen, da die Tour zwei Tage dauert.
Vor dem Pauluskloster stehen heute noch ein Flaschenzug und eine alte Olivenpresse. Der Flaschenzug diente wohl zum Transport des Proviants und um in turbulenteren Zeiten den Besuchern über die Mauer zu helfen.
Heute gelangt man bequem auf normalem Weg ins Klosterinnere und wird von den Mönchen freundlich empfangen.