Предки его были Московскими купцами-старообрядцами; отец Павла Рыбникова умер, когда ему было около 5 лет. В 1844 году Павел Рыбников поступил в 3-ю Московскую гимназию. Учился он все годы блестяще, несмотря на то, что с младших классов после смерти отца вынужден был давать уроки в связи с возникшими материальными трудностями. Закончил гимназию в 1850 году с серебряной медалью. В 1850—1854 годы Рыбников совершил путешествие за границу вместе с К. Т. Солдатенковым и Н. П. Боткиным, причём, по его собственным словам, довольно долго жил в Италии. С 1854 по 1858 год П. Н. Рыбников - студент историко-филологического отделения философского факультета Московского университета. В это время он познакомился с А. С. Хомяковым. Рыбникову это знакомство дало очень много. В. И. Модестов, говоря о широкой образованности его, упоминает, между прочим, и о хорошем знании богословской литературы, — очевидное влияние Хомякова. Через Хомякова П. Н. Рыбников сблизился и с другими славянофилами: Константином и Иваном Аксаковыми, Юрием Самариным (со всеми ими он потом переписывался).
После окончания университета Рыбников давал уроки детям Хомякова и летом 1858 года жил в его Тульском имении Богучаровe. От него он получил рекомендацию в Черниговскую губернию для изучения раскола и записи песен. Там он неожиданно был арестован вследствие его контактов с тамошним старообрядческим купечеством и с принадлежностью к революционному кружку «вертепников» и 3 марта 1859 года сослан в Петрозаводск, а в конце мая был определён там в штат губернской канцелярии. Герцен не преминул по этому поводу поместить в своём «Колоколе» (№ 51, от 1-го сентября 1859 года) заметку, полную сарказма.
В 1863 году он уже был советником Губернского Правления.
В 1859 году Рыбников начал печатание в «Олонецких Губернских Ведомостях» собрание местных былин начальника Олонецких горных заводов Н. Ф. Бутенева и стал глубоко изучать культуру края. Он проехал свыше двух тысяч вёрст от Петрозаводска через Заонежье до границ Архангельской и Вологодской губерний, был в Пудоже и Каргополье; он лично записал двести былин от тридцати народных сказителей; одновременно записывал сказки, песни, причитанья, поверья и многое другое. За одну поездку в мае—июне 1860 года Павел Николаевич записал восемьдесят былин от крупнейших певцов (Леонтия Богданова, Козьмы Романова, Трофима Рябинина, Василия Щеголенкова, Никифора Прохорова и др.). «Песни, собранные П. Н. Рыбниковым» в четырех частях были изданы в 1861—1867 годах и стали известны не только в России, но и за границей.
До Павла Николаевича Рыбникова русская этнография знала в области былин только Киршу Данилова и немногие пьесы в «Памятниках великорусского наречия». Считалось, что найти былины можно только где-нибудь в Сибири — и когда огромный запас их был отыскан недалеко от Санкт-Петербурга, то первым впечатлением ученого мира было изумление и даже недоверие, тем более, что Рыбников лишь в 3-м томе (Петрозаводск, 1864) подробно рассказал о своих странствиях по Олонецкому краю, о том, как был открыт им былинный эпос, как разыскивал он певцов, которых перечислил поименно, с указанием их местожительства и прочего. И после этого оставалась, по-видимому, еще тень сомнения, пока поездка Александра Фёдоровича Гильфердинга не подтвердила существование народнопоэтических богатств Олонецкого края.
Труды Павла Николаевича Рыбникова открыли миру глубину и богатство, сохранённого устной традицией, эпического наследия северных земель Руси.
В апреле 1864 года он был освобождён от надзора с воспрещением жительства в столицах. В 1867 году Рыбников женился на дочери местного чиновника и уехал в польский город Калиш, где состоял вице-губернатором до своей смерти.
Помимо перечисленного, П. Н. Рыбников издал:
Отец — богородский купец Николай Абрамович Рыбников, владелец суконной фабрики в Чудинках близ Купавны.
Сестра — Софья Николаевна (1836—1911), замужем за А. А. Карзинкиным.