Родился 27 июня 1821 года в усадьбе Щетинино, Костромская губерния в семье помещика, отставного унтер-лейтенанта Российского флота Александра Леонтьевича Перелешина.
В 1832 г. вслед за старшим братом Михаилом поступил кадетом в Морской кадетский корпус, по окончании которого в 1835 году гардемарином отправлен плавать в Балтийское море на фрегате «Нева», а через два года в декабре 1837 года произведён в мичманы с назначением в Черноморский флот. В 1838—1853 гг. на разных судах флота крейсировал у абхазских берегов, перевозил войска и грузы по черноморским портам, занимался гидрографическими работами. В 1839 г., находясь на линейном корабле «Султан Махмуд», отличился в десантной высадке при взятии местечка Су-баши на Кавказском побережье, за что был удостоен ордена Святой Анны 4-й степени с надписью «За храбрость». В 1840 году занимался съёмкой берегов на шхуне «Забияка». В 1843 г. произведён в лейтенанты, в 1852 г. — в капитан-лейтенанты. В середине 1853 г. назначен старшим офицером на 120-пушечный линейный корабль «Париж». 18 ноября 1853 года в составе экипажа участвовал в Синопском сражении. Вице-адмирал П. С. Нахимов, командовавший эскадрой Черноморского флота в этом сражении, представил капитан-лейтенанта Перелешина «за отличную храбрость и распорядительность по всем частям управления кораблем» к ордену Святого Георгия 4-й степени. Однако эта награда не была утверждена, и Павел Александрович наряду с командирами палубных батарей был удостоен ордена Святого Владимира 4-й степени с бантом. 20.01.1854 года произведён в капитаны 2-го ранга со старшинством с 18 ноября 1853 года, назначен командующим 35-м флотским экипажем и кораблём «Париж». С 13 сентября 1854 года Павел Александрович состоял в гарнизоне осаждённого Севастополя. Командовал 3-м морским батальоном, сформированным из команд кораблей «Париж» и «Гавриил», и левым флангом 4-го отделения оборонительной линии. За участие в отражении 1-й бомбардировки Севастополя в октябре 1854 г. награждён орденом Святой Анны 2-й степени, за отличие при вылазке на французские позиции в ночь с 10 на 11.03.1855 произведён в капитаны 1-го ранга. 28.03.1855 был контужен в висок, 26.05.1855 — в голову и руку. 30.05.1855г. назначен начальником образованного 5-го отделения оборонительной линии, включавшего 1-й и 2-й бастионы. В конце июля 1855 г. награждён орденом Святого Владимира 3-й степени; в середине августа отбыл на отдых в д. Саблы близ Симферополя и более участия в обороне Севастополя не принимал. Среди других наград за Крымскую войну имел золотое оружие с надписью «За храбрость» (1856 г.). В 1856—1857 годах командовал кораблями «Не тронь меня» и «Владимир», а в 1860 году прикомандирован вследствие плохого состояния здоровья — результат полученных ран — к морскому корпусу. С 16.11.1855 — командир 41-го флотского экипажа и корабля Балтийского флота «Рында». 26 ноября 1855 награждён орденом Святого Георгия 4-й степени за 25 лет выслуги в офицерских чинах. В 1856—1859 гг. командовал на Балтике судами «Не тронь меня» и «Владимир». С мая 1861 г. служил начальником Бакинской морской станции и капитаном над Бакинским портом, в августе 1863 г. произведён в контр-адмиралы. В 1864 г. оставил действительную службу во флоте и в течение двух лет являлся градоначальником Таганрога и Главным Попечителем Азовского купеческого судоходства. Его достижения на новом поприще были отмечены в 1866 году орденом Святого Станислава 1-й степени и переводом в Санкт-Петербург на должность командира Гвардейского экипажа (11.04.1866 — 08.04.1873). В октябре 1867 г. его назначили в Свиту Его Величества, в 1869 и 1871 гг. за «усердно-ревностную службу» наградили орденом Святой Анны 1-й степени и Императорской короной к нему, в 1872 г. Александр II назначил Павла Александровича генерал-адъютантом, в апреле 1873 г. — произвёл в вице-адмиралы. В 1866 г. награждён орденом св. Станислава 1-й степени. 13 августа 1873г. П. А. Перелешина назначили Севастопольским градоначальником, командиром порта и военным комендантом. В 1876 года с Высочайшего соизволения по решению Севастопольской городской думы градоначальнику вице-адмиралу Павлу Перелешину было «поднесено звание Почётного гражданина Севастополя». 1 марта 1876г. по болезни он был уволен с должности Севастопольского градоначальника. За заслуги перед Отечеством в 1876 г. награждён орденом Святого Владимира 2-й степени. С 1881 года — директор Инспекторского департамента Морского министерства, член Комитета морских учебных заведений. В том же году удостоен ордена Белого Орла. В 1883 г. награждён орденом Святого Александра Невского и назначен членом Адмиралтейств-совета, в 1887 г. получил бриллиантовые знаки к ордену Святого Александра Невского; в апреле 1891 г. произведён в полные адмиралы. Удостоен высших наград Российской империи — орденов Святого Владимира 1-й степени (1893) и Святого Апостола Андрея Первозванного (1898). 18 ноября 1898 г., в день 45-летия Синопского сражения Высочайшим именным рескриптом Государя Императора Николая II награждён орденом Св. Апостола Андрея Первозванного. Тогда же присутствовал в Севастополе при открытии в Высочайшем присутствии памятника адмиралу Нахимову.
Скончался 28 февраля 1901 года в Санкт-Петербурге.