Расположен в Инкермане на левом берегу Черной речки, на западной стороне Каменоломенного оврага. На карте И. Батурина в этом месте нанесен храм Св. Софии, поэтому предположительно, что весь пещерный комплекс носил это имя. Традиционно считалось, что монастырь возник в период иконоборческого движения - в VIII-IХ веках, хотя современные исследователи датируют его ХIV-ХV веками, не исключая, однако, строительство вначале скита в более раннее время.
Вблизи этого монастыря имелись несколько отдельных небольших скитов: у станции Инкерман-1, в Георгиевской (Крымской) балке, в Троицкой и Мартыновой балках. Вполне возможно, что их основали монахи монастырей Св. Софии и Св. Георгия (Климента).
В 1886 году описание монастыря с картами и планами составил А.Л. Бертье-Делагард. Монастырский пещерный комплекс был вырублен в скале в два яруса, состоял из четырех храмов, келий и хозяйственных помещений. К нему вели два входа: главный - со стороны реки, от него осталась часть лестницы, второй - от Каменоломенного оврага. Основной храм расположен на высоте семи метров во втором ярусе. Он крестообразный в плане, с плоским потолком, в центре которого вырублен рельефный крест. Рядом имелась церковь меньшего размера с пятью могилами в полу и фрагментами росписей на стенах. Ко времени присоединения Крыма к России монастырь уже не существовал. К 50-летию первой обороны пещерный храм Св. Софии восстановили как храм во имя иконы «Всех скорбящих радость» (архитектор А.М. Вейзен).
В период обороны Севастополя 1941-1942 годов монастырский комплекс сильно пострадал 29 июня 1942 года от взрыва штолен филиала арсенала и подземного госпиталя.