Исполняя Божественное повеление, преподобный оставил вершины Афона, и, взяв с собой двух иноков — Игнатия и Ефрема, отправился с ними с Афона в Солунь. На сей раз Солунь встретила его «как сошедшего с небес ангела». Разузнав о месте, называемом Перистера, Евфимий взял проводников и отправился с ними на указанную ему гору, где и нашел действительно овчарню. Открытые ему свыше признаки указывали, что именно здесь нужно искать развалины прежнего храма, но никто из местных жителей ничего не знал об этом храме. Местные христиане давно имели здесь овчарню, совсем и не помышляя о том, что оскорбляют ее местную святыню. Горько плакал преподобный, видя такое попрание святыни. Начатые им раскопки вскоре же обнаружили все основание храма. Тогда местное население, пораженное таким необычайным даром прозорливости пришедшего к ним старца, с охотою взяло на себя расходы по восстановлению забытого храма. Этим оно хотело как бы загладить грех своего прежнего равнодушия к нему. Так воздвигнут был храм святого апостола Андрея, с приделами: с правой стороны — в честь святого Иоанна Предтечи, а с левой — во имя Евфимия Великого. Но, прежде чем были окончены работы по постройке храма, много трудов и горя пришлось вынести самому преподобному. По злоумышлению демонов, то опрокинулись леса, окружавшие здание, то обрушилась только что выведенная левая сторона его. При таких несчастьях нелегко было преподобному убеждать строителей продолжать начатую постройку. Проводя ночи в молитвах, днем он не отлучался от рабочих, подавая им пример своими собственными работами. Наконец, в 863 году, храм был окончен. При нем, по желанию местного населения, вскоре возник и монастырь, прославившийся впоследствии множеством бывших в нем иноков. Знал преподобный, что многих влечет сюда далеко распространившийся слух о происшедшем здесь чуде, и посему сильно опасался за то, как бы новопостриженные иноки, привлеченные сюда лишь этим слухом и не испытавшие еще сил своих, не оказались неспособными к прохождению многотрудного иноческого жития. Вследствие сего он преподал много поучений этим новоначальным инокам, говорил им об опасностях от диавола, указывал средства для избежания этих опасностей, прославлял святость труда, осуждал пороки и призывал к добродетелям.
— Братия! — поучал иноков преп. Евфимий, — враг наш диавол, по Писанию, как лев, рыкая ходит, чтобы поглотить кого-либо нерадящего о своем спасении: посему будем трезвиться и бодрствовать (ср.1 Пет.6:8). Если мы отреклись от мира, то отсечем пожелания плоти; если мы распяли плоть свою и облеклись в смерть Господню, то да не увлекаемся удовольствиями плотскими и да ходим духом; если для Царствия Небесного облеклись мы в ангельский образ, то и жить должны, как ангелы; если мы действительно любим Господа, то должны хранить Его заповеди. Будем работать своими руками, ибо от праздности и лености мы изнемогаем и ослабеваем для добрых дел, — и тогда бесплодие и оскудение бывает необходимым нашим уделом:
Слушая Евфимия, иноки его обители говорили, что Сам Дух Святой вдохнул в него Божественную благодать, как вдохнул ее в святых апостолов. В числе сих новоначальных иноков был и Василий, впоследствии архиепископ Солунский, благодаря трудам которого сохранилась до нашего времени память о подвигах преподобного Евфимия. Он рассказывает о той Божественной ревности, которою горели поощряемые святым пастырем иноки новой обители. Так, например, когда в обитель их случайно попала одна еретическая книга, то они тотчас же сожгли ее.
За свою благочестивую жизнь Евфимий сподобился дара прозрения будущего и дара чудотворений. Так, вышеупомянутый Василий рассказывает о себе, что ему самим преподобным Евфимием было предречено его епископское звание. На третий день после его пострижения преподобный приходит к нему в церковь, где он должен был пробыть как новопостриженный семь дней, и говорит:
— Василий! хотя я и недостоин светосияния или дара прозорливости, но так как ты и прочие для пользы души притекли под руководство моего недостоинства, то Всеблагий Бог благоволил даровать и мне некую каплю благодати, чтобы, провидев имеющее случиться с вами, я мог говорить вам полезное ко спасению. Итак знай, что ты, по любви к наукам, скоро удалишься из монастыря и будешь епископом: но и тогда поминай меня, как отца твоего, и обитель нашу, и братию.