По преданию, первым насельником огромной скалы (на которой ныне расположен монастырь Варлаам), был монах Варлаам, современник преподобного Афанасия. По имени этого монаха монастырь потом и получил свое название. Храм, посвященный Всем Святым, воздвигли основатели монастыря, которыми, как и в Руссану, были два брата-иеромонаха, преподобные Феофан и Нектарий Аспарас. Они происходили из состоятельной и благородной византийской семьи. Их отец, мать и все три сестры также приняли монашество.
В 1495 году юные братья Аспарас были пострижены своим духовным отцом по имени Савва, с которым они жили вместе на острове Ниси на озере Янина, в области, называемой Гунас, издревле служившей пристанищем для отшельников. В 1505 году, после кончины отца Саввы, они отправились на Святую Гору Афон в монастырь Дионисиат, а на следующий год вернулись в Гунас. Там построили небольшой монастырь в честь святого Иоанна Предтечи, на том месте, где стояла келья их духовного отца. Однако в 1510 году, вследствие политических и церковных интриг со стороны властей, они вынуждены были покинуть свой монастырь и искать прибежища в Метеоре. Наконец, в 1517 году они окончательно обосновались на вершине Варлаам. В их автобиографии, которая хранится в Варлаамской библиотеке, сказано:
Тот факт, что мы какое-то время жили в построенном нами монастыре святого Иоанна Крестителя, не мог не раздражать диавола, для коего невыносимо было видеть, как мы пребываем в мире и согласии с волей Божией... После многих испытаний мы покинули свой дом и пришли в Святой Храм Метеоры, ища мира и уединения. Отцы отдали нам вершину святого Иоанна Предтечи, и мы прожили там семь лет, но потом решили спуститься вниз и поселиться где-нибудь в другом месте, так как места на вершине скалы было очень мало, и из-за ветров, пронизывавших нас насквозь, мы постоянно болели... так что отцы не разрешили нам долее там оставаться. Так мы нашли прекрасное, просторное место на вершине, которая нам очень понравилась. Она называлась Варлаам, в честь монаха, жившего здесь в прошлом. Долгое время здесь никто не жил, поэтому в 1517 году мы начали строить свой монастырь на руинах старого, от которого оставались лишь следы фундамента и часть алтаря. Среди местных иноков и мирян не было ни одного, кто помнил бы, что здесь кто-либо когда-либо жил. Изрядно потрудившись вдвоем, мы с Божией помощью восстановили храм Трех Святителей. Потом, по благодати и благословению Божию, стали приходить и другие иноки, и когда число братии достигло тридцати человек, мы решили воздвигнуть для нужд растущего братства еще одну церковь, больших размеров. Все иноки много и с охотой трудились вместе с нами, и мы построили этот большой храм, посвященный Всем Святым. Он был возведен в 1541 году всего за двадцать дней.
В своем завещании братья добавляют:
...Мы хотели сделать его лучше, больше и красивее, но не решились, боясь завоевателей. В то время ходили слухи, что султан приказал разрушить все христианские храмы. По этой причине мы и не стали строить наш храм так, как нам хотелось, а лишь воздвигли не очень большую церковь для служб. Мы служили в этом храме довольно долго, а потом Господь помог нам построить еще один, с прекрасным крестчатым сводом и двумя куполами. Мы это сделали за свой счет и вложили в строительство огромный труд и усилия. Всемогущий Господь помог нам выстроить и кельи для иноков, и другие сооружения для улучшения условий жизни в монастыре. Кроме того, мы, во славу Божию, приобрели для монастыря святые сосуды, книги и облачения.
Помимо этого, мы отдали монастырю свою собственность: земли, поля, виноградники, сады, мельницы, оливковые рощи... и сделали наш монастырь общежительным. Мы стремились, чтобы иноки сохраняли чистоту сердца, ис¬кренность в отношениях, и порядок во всем...
По воспоминаниям иеромонаха Кассиана, бывшего когда-то настоятелем афонского монастыря Симонопетр, внутренняя отделка храма была завершена три года спустя:
В 1544 году, в девятом часу в субботу 17 дня месяца мая было закончено строительство честного и великолепного храма на священной скале Варлаам. Строительство было предпринято святейшими и преподобнейшими отцами, родными братьями Нектарием и Феофаном за свой собственный счет. К тому времени блаженный Феофан был уже десять месяцев как болен, и болезнь так истощила его силы, что он находился при смерти. Но ему очень хотелось увидеть новый храм, и он охотно и с радостью встал с постели. Несмотря на болезнь, пошел к храму, опираясь на посох, чтобы присутствовать при завершении строительства. Потом воздел руки горе, славя Бога и Всех Святых, коим он посвятил этот храм, благословил и помолился за всю братию, строителей, каменщиков и резчиков по дереву. После этого вернулся в свою келью, перекрестился и лег, обратив лицо на Восток...
Отец Феофан отошел ко Господу через несколько месяцев после того, как увидел плодотворное завершение трудов своей жизни. Его брат, иеромонах Нектарий, умер шестью годами позже.
