In the fifth century A.D., the Empress Eudocia (also spelled Eudoxia) built the great Church of Saint Stephen on the site of today’s monastery of St. Étienne, thereby initiating a wave of development in the area. It seems that the Garden Tomb cave was emptied of its original contents at that time and prepared for use as a Christian burial site—perhaps for the clergy of St. Stephen’s church. The plan of the cave was adapted to the customs of the new occupants: in place of burial benches on which to lay the deceased, burial troughs were cut out, and Christian symbols were daubed on the walls in red paint.

Still later, in the Middle Ages, the area of the Garden Tomb became a stable for the mules and donkeys of the Crusaders. To this stage, we may attribute the water cistern in the court of the Garden Tomb, as well as the soft limestone figurines of horsemen found by Beckholt in his excavations. During this period a series of vaults was built against the escarpment into which the cave is hewn. The vaults were built to create a complex of mule stables used by the Crusaders. In order to create vaults that were high enough, but would not extend above the escarpment, the Crusader builders lowered the rock surface in front of the cave entrance. As a result, today one must step up to enter the caves. Outside the entrance to the cave, a channel was cut into the rock face; this channel was most probably used in connection with the Crusader complex of vaulted structures. This late rock-cut channel was subsequently identified by 19th- and early 20th-century defenders of the authenticity of the Garden Tomb as the groove for the rolling stone covering Jesus’ burial cave mentioned in the Gospels (Matthew 27:60).