Paulus Ludolf Melchers war der Sohn wohlhabenden Kaufmanns aus Münster in Westfalen.
Nachdem er 1829 das Abitur gemacht hatte studierte er Philosophie in Münster und Jura in Bonn . 1833 legte er sein Staatsexamen ab und leistete anschließend bis 1834 seinen Wehrdienst ab. Nach seinem Wehrdienst schlug er juristische Berufslaufbahn ein. Entschied sich jedoch 1839 für den Priesterberuf und studierte in München Theologie .
Papst Pius IX. bestellte ihn 1858 zum Apostolischen Provikar für die Nordischen Nach dem Scheitern der regulären Wahlverhandlungen wurde als Kompromißkandidat am 8. Januar 1866 zum Erzbischof von Köln ernannt. 1867 wurde Melchers der Vorsitzende der deutschen in Fulda .
Melchers stand der Frage einer Dogmatisierung Unfehlbarkeit des Papstes reserviert gegenüber. Er nahm Ersten Vatikanischen Konzil teil. Er hielt die Dogmatisierung der für nicht opportun und stimmt der Konzilsvorlage bedingt zu. Vor der Abschlußabstimmung des Konzils 18. Juli 1870 reiste er wie 54 andere Bischöfe Rom ab. Er beugte sich jedoch den und verkündigte das Infallibilitätsdogma in seiner Diözese .
Der dem Infallibilitätsdogma folgende Kulturkampf brachte Melchers verschiedene Geldstrafen sowie 1874 eine mehrmonatige Haftstrafe im Kölner Gefängnis ein. 1875 entzog er sich steckbrieflich gesucht einer Verhaftung durch seine Flucht in die Niederlande . Er versuchte von dort aus dem Exil in der niederländischen Provinz Limburg das Erzbistum Köln zu leiten.
Bei der Feier zur Fertigstellung des Kölner Doms im Januar 1880 an der auch der deutsche Kaiser Wilhelm I. teilnahm war Melchers nicht zugegen.
1884 ging er nach Rom wo ihn 27. Juli 1885 Papst Leo XIII. zum Kardinal ernannte. Melchers legte daraufhin Amt als Erzbischof von Köln nieder. In konnte er jedoch auf Grund seiner Gesundheit wirksame Tätigkeit ausüben. Im Jahr 1892 trat er mit Erlaubnis des Papstes Gesellschaft Jesu bei.
Paulus Ludolf Melchers starb am 14. 1895 in Rom. Seine sterblichen Überreste wurden Köln überführt und dort am 27. Dezember 1895 in der bischöflichen Gruft des Kölner beigesetzt.