La prima menzione storica del Muristan si ha nel 600: all'abate Probus fu commissionata da papa Gregorio I la costruzione di un ospitale a Gerusalemme per avere cura dei pellegrini cristiani in Terra santa. Nel IX secolo Carlo Magno, imperatore del Sacro Romano Impero, ingrandì l'ostello di Probus e vi aggiunse una biblioteca. Circa due secoli dopo, nel 1005, l'Imām fatimide al-Hākim distrusse l'ostello assieme con altri tremila edifici. Fece portare ai cristiani, appese al collo, delle croci di legno, lunghe circa un metro e larghe mezzo. Malgrado ai cristiani non fosse permesso di acquistare schiavi, maschi o femmine, e godessero di pochi privilegi, ad essi era concesso di usare i cavalli a condizione che essi cavalcassero con la sella di legno e finimenti disadorni.