Предки его были Московскими купцами-старообрядцами; отец Павла Рыбникова умер, когда ему было около 5 лет. В 1844 году Павел Рыбников поступил в 3-ю Московскую гимназию. Учился он все годы блестяще, несмотря на то, что с младших классов после смерти отца вынужден был давать уроки в связи с возникшими материальными трудностями. Окончил гимназию в 1850 году с серебряной медалью[2]. В 1850—1854 годы Рыбников совершил путешествие за границу вместе с К. Т. Солдатенковым и Н. П. Боткиным, причём, по его собственным словам, довольно долго жил в Италии. С 1854 по 1858 год П. Н. Рыбников — студент историко-филологического отделения философского факультета Московского университета. В это время он познакомился с А. С. Хомяковым. Рыбникову это знакомство дало очень много. В. И. Модестов, говоря о широкой образованности его, упоминает, между прочим, и о хорошем знании богословской литературы, — очевидное влияние Хомякова. Через Хомякова П. Н. Рыбников сблизился и с другими славянофилами: Константином и Иваном Аксаковыми, Юрием Самариным (со всеми ими он потом переписывался)[3].
После окончания университета Рыбников давал уроки детям Хомякова и летом 1858 года жил в его Тульском имении Богучаровe. От него он получил рекомендацию в Черниговскую губернию для изучения раскола и записи песен. Там он неожиданно был арестован[3] вследствие его контактов с тамошним старообрядческим купечеством и с принадлежностью к революционному кружку «вертепников».
С 3 марта 1859 года по 1866 год отбывал ссылку в Петрозаводске[4], где в конце мая был определён в штат олонецкой губернской канцелярии[2]. Герцен не преминул по этому поводу поместить в своём «Колоколе» (№ 51, от 1-го сентября 1859 года) заметку, полную сарказма. В 1863 году был назначен советником олонецкого Губернского Правления.
В 1859 году Рыбников начал печатание в «Олонецких Губернских Ведомостях» собрание местных былин начальника Олонецких горных заводовН. Ф. Бутенева и стал глубоко изучать культуру края. Он проехал свыше двух тысяч вёрст от Петрозаводска через Заонежье до границ Архангельской и Вологодской губерний, был в Пудоже и Каргополье; он лично записал 165 текстов на 50 сюжетов былин от тридцати народных сказителей; одновременно записывал сказки, песни, причитанья, поверья, руны и ёйги. За одну поездку в мае—июне 1860 года Павел Николаевич записал восемьдесят былин от крупнейших певцов[2] (Леонтия Богданова, Козьмы Романова, Трофима Рябинина, Василия Щеголенкова, Никифора Прохорова и др.). «Песни, собранные П. Н. Рыбниковым» в четырёх частях были изданы в 1861—1867 годах и стали известны не только в России, но и за границей.
До Павла Николаевича Рыбникова русская этнография знала в области былин только Киршу Данилова и немногие пьесы в «Памятниках великорусского наречия». Считалось, что найти былины можно только где-нибудь в Сибири — и когда огромный запас их был отыскан недалеко от Санкт-Петербурга, то первым впечатлением учёного мира было изумление и даже недоверие, тем более, что Рыбников лишь в 3-м томе (Петрозаводск, 1864) подробно рассказал о своих странствиях по Олонецкому краю, о том, как был открыт им былинный эпос, как разыскивал он певцов, которых перечислил поименно, с указанием их местожительства и прочего. И после этого оставалась, по-видимому, ещё тень сомнения, пока поездка Александра Фёдоровича Гильфердинга не подтвердила существование народнопоэтических богатств Олонецкого края.
Труды Павла Николаевича Рыбникова открыли миру глубину и богатство, сохранённого устной традицией, эпического наследия северных земель Руси.
Был редактором справочного издания «Памятная книжка Олонецкой губернии» (1864, 1965, 1867, 1868—1869). Являлся инициатором создания в 1860 году городской публичной библиотеки в Петрозаводске (ныне — Национальная библиотека Республики Карелия)[4].
Награждён золотой медалью Русского географического общества и Демидовской премией (1864).
В апреле 1864 года он был освобождён от надзора с воспрещением жительства в столицах[5]. В 1867 году Рыбников женился на дочери местного чиновника[6] и уехал в польский город Калиш, где состоял вице-губернатором до своей смерти. Дослужился до чина действительного статского советника[7]. Похоронен на греко-российском кладбище в Калише.
Базанов В. Г. П. Н. Рыбников в Карелии // Народная словесность. — Петрозаводск, 1947
Карелия: энциклопедия: в 3 т. / гл. ред. А. Ф. Титов. Т. 3: Р — Я. — Петрозаводск: ИД «ПетроПресс», 2011. С. 48 — 384 с.: ил., карт. ISBN 978-5-8430-0127-8 (т. 3)
Разумова А. П. Из истории русской фольклористики. — М.;Л., 1954
Разумова И. А. П. Н. Рыбников // Песни, собранные П. Н. Рыбниковым. — Петрозаводск, 1989. Т. 1.