О подвигах отшельника узнали в окрестности. Стали приходить к нему в уединение ради поучения, ибо слову его дана была премудрость, разум и утешение. И слышавшие наставления и видевшие житие преподобного почитали его уже не как человека, а как Ангела Божия. Многие просили его разрешения поселиться с ним в пустыне и пользоваться его руководством на пути спасения. Преподобный долго отказывал им, называя себя недостойным быть учителем, но уступил неотступным просьбам и стал принимать братию и устанавливать правила общего жития. Однако, он действовал не как старейшина и начальник, но как самый последний из братии – тихо и кротко. Он нисколько не послаблял требований иноческого устава, но умел заставить сподвижников выполнять его добровольно и охотно. Своей кротостью, долготерпением в обхождении, своим примером и попечительностью о каждом преподобный Павел объединял всю братию. Его поучения были исполнены удивительной простоты и мягкости чувства. «Чада, – говорил он, – сколько сил имеете, подвизайтесь о своем спасении, прежде чем наступит время, когда принуждены будем плакать о нынешней лености. Если кто скажет, что немощен и слаб он, я отвечу: а ты по силе своей положи начало подвигу, и Бог даст тебе помощь на все доброе. Разумея это, воспрянем от сна духовного, пойдем тесным путем, ведущим в жизнь вечную, предадим телеса свои на труд, и на пост, и на молитву, и на воздержание, и на поклоны: с усилием достигается Царство Небесное. Пожалеть придется, если из-за своей лености мы лишимся вечной жизни: понудим же себя в этом кратком веке. Не будем лениться, братия, и угождать тленному телу, не будем забывать, что всякий увлеченный временным житием сим лишится жизни вечной. Раскроем книги и прочтем жития святых отцов и найдем много полезного. Сколько отцы исправляли себя, сколь были смиренны, до какого изнеможения и уничижения себя доводили! С какой тихостью и чистотою жили они! Бдение, молитва, покаяние, слезы; если мы не потерпим этого, никогда не будем оправданы. Напишем же на скрижалях сердец наших наставления, какие оставили нам святые отцы, да не будут нам во осуждение словеса их в день судный».
Собравшееся возле преподобного Павла братство не имело сначала своей церкви. Построение церкви и с нею образование монастыря сопровождалось особыми знамениями. Как-то ночью на молитве преподобный слышит звон на том месте, где стоит теперь его монастырь. И это повторялось не раз и не два, а многократно, причем звон в праздники отличался от звона в будни. Преподобный долго почитал слышимый им звон за мечтание. Но вот случилось, что он услышал звон в пасхальную светоносную ночь, звон сильный. Открывает он оконце своей келлии и видит свет, сияющий на месте, где ныне стоит церковь Живоначальной Троицы. Слышание звона и видение света исполнили сердце его великой радостью и убедили, что благоволение Божие к месту сему несомнительно и что здесь прославится святое имя Божие. Поведал он обо всем братии, и все славили и благодарили Бога.
Взяв одного из братии, Павел отправился в Москву испросить благословение у митрополита Фотия на построение церкви во имя Живоначальной Троицы. Митрополит сперва не только не исполнил просьбы преподобного, но и обошелся с ним сурово, говорил немилостиво и отказал преподобному в просьбе построить церковь и открыть монастырь, вероятно, принимая подвижника за тех людей, которые строили монастыри не по искреннему влечению к монашеству, а ради телесного покоя, чтобы получать доходы и управлять братией в сане игумена. Уверенный в правоте своего прошения, Павел скромно заметил, что храм будет устроен, если то угодно Богу, и удалился. В следующую ночь владыка Фотий по особому внушению уразумел, что несправедливо суров был к человеку Божию, и немедленно послал за ним. Не без труда нашли преподобного в одном из московских монастырей и привели к митрополиту. Фотий встретил его с честью в дверях своего дома и стал подробно обо всем расспрашивать, испросив прощение за вчерашний прием. Павел поведал владыке откровенно, в чем нуждался. И речи преподобного и кроткий нрав его расположили к нему святителя; он не только дал просителю благословение на построение церкви и монастыря, но и вошел в это дело личным участием, преподал Павлу наставления о том, как подобает устроить спасение душ человеческих, и вручил ему богатую милостыню, между прочим, одежду свою. Последнюю смиренный отшельник едва согласился принять.
Отклонил от себя преподобный и честь священства, так что поставлен был на эту ступень ученик его Алексий.