По окончании Морского кадетского корпуса в 1835 г. гардемарином отправлен плавать в Балтийское море на фрегате «Нева», а через два года произведён в мичманы с назначением в Черноморский флот.
Плавая в Чёрном море на разных судах, в 1839 г. участвовал в десантной высадке при занятии местечка Субаши, за которую награждён орденом св. Анны 4-й степени с надписью «за храбрость».
В 1840 г. занимался съёмкой берегов на шхуне «Забияка». За участие в 1853 г. на корабле «Париж» в Синопском сражении награждён орденом св. Владимира 4-й степени с бантом. При обороне Севастополя находясь в должности командующего 41-м флотским экипажем состоял начальником 5-го отделения оборонительной линии.
Контуженный 28 марта 1855 в левый висок, 26 мая в голову и руку, за выдающуюся храбрость и распорядительность в делах с неприятелем награждён орденами св. Анны 2-й степени (1854 г.), св. Владимира 3-й степени с мечами (1855 г.) и 26 ноября 1855 г. «за беспорочную выслугу 25 лет в офицерских чинах» орденом св. Георгия 4-й степени, а 29 февраля 1856 г. был удостоен того же ордена 3-й степени:
Среди других наград за Крымскую войну имел золотое оружие с надписью «За храбрость» (1856 г.). В 1856—1857 гг. командовал кораблями «Не тронь меня» и «Владимир», а в 1860 г. прикомандирован вследствие плохого состояния здоровья — результат полученных ран — к морскому корпусу.
В следующем году назначен начальником Бакинской морской станции и капитаном над портом, 30 августа 1863 произведён в контр-адмиралы, а 15 октября 1867 зачислен в Свиту Его Величества контр-адмиралом. Затем последовательно занимал должности Таганрогского градоначальника, командира Гвардейского экипажа (с 11 апреля 1866), Севастопольского градоначальника, командира порта и коменданта.
В 1866 г. награждён орденом св. Станислава 1-й степени.
В июне 1875 г. вместе с городским головой Севастополя г-ном М.И.Кази выступил за сохранение оборонных сооружений, возведённых в период героической защиты Севастополя, как исторического памятника. 28 ноября 1875 г. Император Александр II разрешил подписку для сбора средств на это мероприятие по всей России. Явился одним из главных создателей Музея Черноморского Флота в Севастополе, председателем Комитета которого оставался до самой своей кончины. Вместе с городским головой г-ном М.И.Кази много сделал для возрождения Севастополя, упрочения его благосостояния. Они первые энергично и успешно хлопотали о развитии коммерческого значения города, учредили реальное училище, отделение Государственного банка, добились ассигнования 300 тыс. рублей на постройку 10-ти хлебных городских магазинов, 50 тыс. рублей на постройку больницы и, самое главное по мнению городского руководства, добились предоставления Южной бухты для торгового судоходства. В 1876 г. решением городской Думы Севастополя удостоен почётного звания Почётного гражданина города Севастополя. Как писала крымская газета, сообщавшая о кончине адмирала П.А.Перелешина: "…Во всех делах покойный адмирал принимал самое горячее участие, и его сердечному отношению к нуждам города Севастополь обязан был своим процветанием. Благодарное население, в лице своих представителей – гласных Думы и решило одновременно поднести звание Почётных граждан градоначальнику П.А.Перелешину и городскому голове М.И.Кази. В том же 1876 году на это последовало Высочайшее соизволение" ("Крымский вестник", 4 марта 1901 г.).
В 1881 г. в чине вице-адмирала и звании генерал-адъютанта (с 1 января 1872 г.) назначен директором инспекторского департамента Морского министерства, а затем членом комитета морских учебных заведений и главного военно-тюремного комитета.
В 1883 г. назначен членом адмиралтейств-совета, в начале 1880-тых годов возглавлял специальную Комиссию, созданную для составления документа, с целью упорядочения прохождения службы офицерского состава флота. Комиссией под его руководством было разработано "Положение о морском цензе" и "Положение о чинах по Адмиралтейству", утверждённые в 1885 г. 23 декабря 1887 г. - пожалованы бриллиантовые знаки ордена Св. Александра Невского – за пятидесятилетнюю отлично-усердную службу в офицерских чинах.
21 апреля 1891 г. произведён в адмиралы. 22 августа 1891 г. – вручён «Знак отличия за 50 лет беспорочной службы».
В 1895 г. был Высочайше командирован для присутствия при церемонии открытия памятника адмиралу Корнилову на Малаховом кургане.
14 мая 1896 г. - в день Священного Коронования Государя Императора Николая II Высочайше пожалован перстнем с портретом Его Императорского Величества.
В «Морском сборнике» за 1858 г. напечатана его статья «Несколько слов о характере П. С. Нахимова».
18 ноября 1898 г., в день 45-летия Синопского сражения Высочайшим именным рескриптом Государя Императора Николая II награждён орденом Св. Апостола Андрея Первозванного. Тогда же присутствовал в Севастополе при открытии в Высочайшем присутствии памятника адмиралу Нахимову.
Имел все российские ордена и многие иностранные.
Павел Александрович Перелешин был женат на Александре Михайловне Корсаковой, дочери Михаила Матвеевича Корсакова, потомственного дворянина Костромской губернии, отставного коллежского советника, (между прочим, известного декабриста). Женился Павел Александрович в 1858 г. У них было 6 детей, в том числе 2 сына - Михаил и Павел (род. 13 февраля 1865 г.), и 4 дочери – Александра (род. 19 июня 1859 г.), Екатерина (род. 9 октября 1861 г.), Надежда (род. 3 апреля 1863 г.) и Мария (род. 18 мая 1866 г.).
Умер 28 февраля 1901 г. в Санкт-Петербурге. Отпевание прошло 3 марта 1901 г. в Никольском Богоявленском соборе, где была совершена "…заупокойная литургия в присутствии Высочайшего Двора, Адмиралитета и Генералитета. Гроб до крыльца провожал Император, затем гроб был поставлен в траурный вагон для отправки в Севастополь." ("Крымский вестник", № 62, четверг, 8 марта 1901 г.). По Высочайшему повелению Государя Императора Николая II останки П.А.Перелешина, как героя Севастопольской обороны, были торжественно доставлены в Севастополь и похоронены во Владимирском соборе, в Адмиральской усыпальнице.
В 2008 г. Городской совет Севастополя принял решение о присвоении имени адмирала Российского флота П.А.Перелешина новой набережной, которая тянется от яхт-клуба в Мартыновой бухте до набережной Адмирала Клокачева.
Брат Павла Александровича, Михаил Александрович, также принимал участие в Севастопольской обороне и был награждён за отличие орденом св. Георгия.