Похоронили ев. Евфросинию вблизи храма Святой Богородицы в Феодосиевом монастыре. Мощи ее пролежали в этом древнем монастыре до 1187 г. – в тот год их забрали оттуда насельники русского иерусалимского монастыря, которым, как и всем христианам, пришлось покинуть Иерусалим, когда Святая Земля была завоевана Саладином. Мощи ев. Евфросинии монахи взяли с собой на родину, где оставили их в дальних пещерах Киево-Печерской лавры. Там мощи пребывали до тех пор, пока в 1910 году не были торжественно перенесены в Полоцк, в Свято-Евфросиниевский монастырь. Однако память о пребывании мощей преподобной в лавре Феодосия Великого на Святой Земле сохраняется и по сей день: храм неоднократно перестраивался, но место, где лежали мощи преп. Евфросинии, справа от входа, всегда отмечено ее иконой.
В XIII столетии все изменилось. В 1204 г. крестоносцы разграбили Константинополь, и для русских изменилась налаженная веками система торговли и контактов с Византией. На Руси это – время раздробленности и междоусобных распрей, в результате которых вся страна стала легкой добычей татаро-монгол в 1237–1241 гг. Под татаро-монгольским игом Русь оставалась до «стояния на Угре» в 1480 году.
Конечно, в такой ситуации русским было не до паломничеств. С конца 30-х годов XIII в. и до середины XIV в. известно не больше десятка русских путешествий в Константинополь, да и то это были по большей части «командировки» русских архиереев ко Вселенскому патриарху. До Святой Земли, которая постепенно переходила в руки мусульман, русские тогда не доходили вовсе. Связи с Византией и Святой Землей стали возрождаться во второй половине XIV в.
В середине XV в. ситуация поменялась вновь. В 1453 г. Константинополь был захвачен турками-османами, и Византийская империя прекратила свое существование. На церковной ситуации это вроде бы и не сказалось: для решения важных вопросов русские по-прежнему обращались в Константинополь, но теперь Московская Русь оказалась единственным свободным православным государством. Сюда стали обращать свои взоры христиане, оказавшиеся под мусульманским владычеством. Поток русских паломников в Константинополь постепенно сокращался: Святая София и многие другие христианские храмы стали мечетями.
В начале XVI века весь Ближний Восток и Северная Африка оказались в составе Османской империи, как уже раньше произошло с Малой Азией и Балканами. С одной стороны, это было не слишком удобно для русских путешественников, так как Россия и Османская империя всегда пребывали либо в состоянии войны, либо в атмосфере очень натянутого мира. С другой стороны, теперь весь христианский Восток находился во власти одного государства, и посетить разные страны Ближнего Востока стало легче, ведь они больше не были разделены границами.