Der Heilige Paulus von Theben soll 90 Jahre in einer Höhle gelebt haben. Nach seinem Tod Mitte des 4. Jahrhunderts wurde diese zunächst zu einer Pilgerstätte und entwickelte sich schließlich zu einem Kloster. Heute befindet sich in der Höhle die Kirche St. Paul. Das gesamte Kloster ist aufgrund mehrerer Angriffe in der Vergangenheit von einer hohen Mauer umgeben. Die Kirchengeschichte ist vor allem durch zeitgenössische Berichte bekannt, da archäologische Untersuchungen bisher nicht durchgeführt wurden. Dadurch sind die Anfänge des Klosters nur schwer greifbar. Im Jahr 570 wurde die Höhle des hl. Paulus von einem anonymen Pilger besucht, der von der dortigen Wasserquelle berichtet, jedoch kein Kloster erwähnt. Erst im 12. Jahrhundert findet sich beim Kopten Abu al-Makarim eine Beschreibung des Klosters.