Активно поддерживал противников реформ патриарха Никона.
Почитается старообрядцами святым в лике священномученика.
Родился в селе Колычево Княгининского уезда Нижегородской области в семье сельского священника. Принял постриг в Макариевском Желтоводском монастыре, с 1636 года монастырский казначей. По некоторым историческим данным известно, что епископ Павел постоянно проживал в городе Коломне. Во второй половине 1640-х годов иеромонах Павел входит в московский Кружок ревнителей благочестия вместе с протопопом Аввакумом, архимандритом (будущим патриархом) Никоном, епископом Илларионом Рязанским (будущим гонителем «раскольников») и прочими.
С 1651 года — игумен Пафнутиево-Боровского монастыря. В 1652 году был одним из 12 претендентов на престол патриарха. Патриархом по настоянию Алексея Михайловича становится Никон. В этом же году Никон возвёл Павла в сан епископа Коломенского и Каширского.
В 1653 году начаты репрессии в отношении противников реформ Никона. В 1654 году для узаконивания своих действий патриарх Никон собирает собор с тщательно отобранными участниками, среди которых был Павел Коломенский. На соборе Павел открыто выступил в защиту «старых книг», а под соборными постановлениями вместо подписи написал: «Если кто от преданных обычаев святой соборной церкви отъимет, или приложит к ним, или каким-либо образом развратит, анафема да будет». Никон избил Павла на соборе, сорвал с него мантию, без соборного суда лишил епископской кафедры и сослал в Палеостровский монастырь. В отдельных старообрядческих источниках упоминается «великий собор», созванный по благословлению епископа Павла в Куржецком монастыре (рядом с местом ссылки Павла Коломенского).
В 1656 году Павел переведён под более строгий надзор в новгородский Хутынский монастырь, где и был, по-видимому, убит. Официальное объяснение звучало так: «никто не видел, как погиб бедный: зверями похищен или в в реку упал и утонул». В старообрядческих источниках утверждается, что Павел начал юродствовать Христа ради (единственный в церковной истории пример юродивого-епископа). Традиционно юродивые считались неприкосновенными на Руси, а к их словам прислушивались как в народе, так и во власти, вплоть до царя. Узнав об этом, Никон будто бы подослал наёмных убийц и епископ Павел Коломенский был сожжён в срубе 3 апреля (по старому стилю) 1656 года.
Московский собор 1666—1667 годов, судивший Никона, вменил ему извержение из сана и смерть епископа Павла: «Да ты же, Никон, коломенского епископа Павла без собора, вопреки правил, низверг и обругал и сослал его в ссылку и там его умучил, и то тебе низвержение вменится в убийство».