Aus hessischer jüdischer Familie. Sohn des Viehhändlers und Haarkäufers Heinemann P. (1801/03-1889) und dessen Ehefrau Sara, geb. König (1810-1863). Der Vater war zugleich Religionslehrer, Vorbeter und Schächter (Schochet) am Ort. Verheiratet (seit 1869) mit Rosalie, gen. Rosa, P., geb. Glans (1851-1901). Mindestens elf Kinder (acht Töchter und drei Söhne); weitere drei Kinder sollen vor Übersiedlung der Familie nach Ffm. 1882 verstorben sein. Vater von Theodor P. Großvater von Richard Plant.
Rabbinische Ausbildung in Ffm., Hamburg und Mainz. Studium der Philosophie und orientalischen Sprachen in Leipzig. 1867 Promotion in Leipzig mit einer Arbeit über „Flavius Josephus und die Bibel“. Seit 1868 Rabbiner, zunächst in Schwersenz/Posen, von 1872 bis 1882 in Karlsbad. Louise von Rothschild, die in Karlsbad zur Kur weilte, soll ihn dort als hervorragenden Kanzelredner „entdeckt“ und nach Ffm. empfohlen haben. Seit 1882 wirkte P. als zweiter (liberaler) Rabbiner der Israelitischen Gemeinde an der Hauptsynagoge in Ffm., zunächst neben Nehemias Brüll, der zwar ein bedeutender Gelehrter war, aber bisher kaum Kontakt zur Gemeinde gefunden hatte. Als Seelsorger sollte P. die fehlende Publikumsnähe herstellen, was ihm auch gelang: Er war in Ffm. und in der Gemeinde sehr beliebt. Mit der Baronin Rothschild und ihrer Familie blieb er auch in Ffm. besonders verbunden. Wegen einer Augenerkrankung, die zur vollständigen Erblindung führte, wurde P. 1902 pensioniert. Sein Nachfolger als Rabbiner wurde Caesar Seligmann, der zwölf Jahre später – wie auch Bürgermeister Luppe – am Grab P.s sprach.
Mitglied im „Comité der Gesellschaft zur Erforschung jüdischer Kunst-Denkmäler“ (1897) und in der Loge zur aufgehenden Morgenröthe.
Zahlreiche Trauerreden von P. sind im Druck erschienen, u. a. anlässlich der Trauergottesdienste für die Kaiser Wilhelm I. und Friedrich III. in der Hauptsynagoge (beide 1888) sowie zum Gedächtnis für Hannah Louise von Rothschild (1892), Louise von Rothschild (1894) und Theodor Stern (1900). Auch übersetzte P. die Schrift „Me-ḥayil el ḥayil. Zur Belehrung und Erbauung für Schule und Haus“ (1892) von Clementine von Rothschild (1845-1865), zu deren Erinnerung die Mutter Louise von Rothschild das Clementine-Mädchen-Spital (heute: Clementine Kinderhospital) stiftete.
Von den drei bekannten Söhnen aus der Ehe von Rudolf und Rosa P. wurden zwei Mediziner, der Gastroenterologe Theodor P. (1874-1938), der nach dem Novemberpogrom 1938 unter ungeklärten Umständen ums Leben kam, und der Pathologe und Krebsforscher Alfred P. (1888-1962), der bereits 1919 in die USA übersiedelte. Der mittlere Sohn Georg P. (1883-1950) war promovierter Chemiker, wandte sich aber 1908 dem Musiktheater zu, zunächst als Kapellmeister, Regisseur und Dramaturg, und führte den Bühnennamen Georg Pauly, den er 1926 auch offiziell annahm. Er war u. a. Spielleiter und Dramaturg an der Opernbühne des Stadttheaters Breslau (1917-22), stellvertretender Intendant, Oberspielleiter und Dramaturg an der Städtischen Oper Berlin (1823-28) und Intendant des Stadttheaters Saarbrücken (1929-33); seit den 1920er Jahren war als Gastregisseur an renommierten Opernbühnen im Ausland tätig. 1935 emigrierte Georg Pauly nach Buenos Aires, von wo aus er seine Tätigkeit als Opernregisseur und -dirigent in Süd- und Mittelamerika erfolgreich fortsetzte; zuletzt war er Oberspielleiter am Nationaltheater und Dozent für Theaterwissenschaft an der Universität in La Plata. Sein Sohn aus der Ehe mit der Pianistin Hermine Pauly-Correns (1887-1973) war der Musikwissenschaftler und Geiger Reinhard Georg Pauly (1920-2019), der seit seiner Emigration aus Berlin 1937 in den USA lebte und arbeitete.
Zwei der acht namentlich nachgewiesenen Töchter von Rudolf und Rosa P., Adele (1876-1886) und Paula (1882-1903), starben früh. Die älteste Tochter, Frida (seit 1895 verh. Mechanik, 1873-1942), kam im Konzentrationslager Theresienstadt ums Leben. Die fünf anderen Töchter überlebten die NS-Zeit in der Emigration: Ella (seit 1900 verh. Baer, seit 1915 in 2. Ehe verh. Werner, 1880-1964) in den USA, Flora (seit 1900 verh. Gut, 1881-1964) in Schweden, Alice (verh. Kortschak, 1884-1972) in Honolulu, Hedwig (seit 1910 verh. Simon, 1885-1949) in den USA und Martha (seit 1914 verh. Schulz, 1887-1977) in England. Alice Kortschak war ihrem Mann, dem Violinisten Hugo Kortschak (1884-1957), schon um 1908 in die USA gefolgt; aus der Ehe stammte u. a. der Biologe Hugo Peter Kortschak (1911-1983), der auf dem Gebiet der Pflanzenphysiologie arbeitete und erstmals die C₄-Photosynthese biochemisch untersuchte und beschrieb (1957). Martha Schulz, die mit dem Rechtswissenschaftler und -historiker Fritz Heinrich Schulz (1879-1957) verheiratet war, hatte zusammen mit dem jüngsten Bruder Alfred P. studiert und war ebenfalls promovierte Medizinerin.