Уже незадолго до кончины Феодосия положено было начало основанию каменной церкви на том месте, где находится и теперь главный храм Печерской обители. Средства для этого, на первый раз, доставлены были одним варягом, по имени Шимон. Об нем сохранился такой поэтический рассказ:
Шимон был изгнан из отечества своими дядями и отправился на корабле служить в Русь. Был у него оставшийся от отца крест в десять локтей с поясом — по одним известиям в 50, по другим в 8 гривен — и с золотым венцом на главе Распятого. Шимон захватил с собою пояс и венец, когда уходил из родины. Тогда был ему такой глас: «Не возлагай этого на главу свою, а неси на уготованное место, где строится церковь Матери Моей, и отдай в руки преподобного Феодосия, а он повесит над жертвенником». После этого видения, во время плавания его по Балтийскому морю в русскую землю, сделалась буря. Шимон испугался и полагал, что Бог наказывает его за то, что он взял украшение с Христова образа, и стал в этом каяться; тогда увидел он на воздухе изображение церкви и услышал голос: «Вот церковь, которая будет создана во имя Божией Матери, а ты будешь положен в ней. Размер поясом двадцать локтей в высоту, тридцать в длину и тридцать в ширину». Несмотря на это, по прибытии в Киев, Шимон долго не строил церкви, но ему было снова чудное видение. Уже по смерти Ярослава, при котором он приехал в Русь, Шимон с его сыновьями: Изяславом, Святославом и Всеволодом, отправляясь против половцев, обращался к Антонию за благословением.
Преподобный Антоний сказал: «О, чадо! Многие падут от острия меча, многие будут попираемы и уязвляемы, многие потонут в воде, а ты останешься спасен; тебе суждено лежать в печерской церкви, которая здесь построится». Русские были поражены на Альте. Шимон был ранен, лежал на поле посреди трупов и умирающих и вдруг увидел в воздухе изображение той же церкви, которая являлась ему над балтийскими водами. Он исцелился от ран, рассказал Антонию о видениях и отдал ему венец и пояс, Антоний переименовал Шимона в Симона и передал его дар Феодосию. Симон очень полюбил Феодосия и доставил ему много средств для постройки новой церкви. Это было в 1073 году.
Симон явился после того к Феодосию и сказал ему: «Дай мне, отче, слово, что душа твоя благословит меня не только в этой жизни, но и по смерти моей и твоей».
«Это прошение выше силы моей, — отвечал Феодосий. — Но если по моем отшествии от мира устроится эта церковь, если будут уважать в ней предания и мои уставы, то это будет тебе знаком, что я имею дерзновение у Бога».
