Han var søn af forvalter over Sorø Akademis gods Caspar Peter Müller (død 1776) og Anna født Paludan (død 1805). Faderen døde, da sønnen var fire år gammel; men morens værge, professor Laurits Laurberg Kongslev, tog sig af drengen og lod ham undervise sammen med sine egne børn. Han flyttede siden med moren til København og blev privat dimitteret 1789. 1793 tog han teologisk embedseksamen, blev lærer ved Waisenhuset og 1799 sognepræst for Thise Sogn i Viborg Stift. 1801 forflyttedes han til Kerteminde og Drigstrup, og 1819 blev han stiftsprovst og sognepræst ved Sankt Knuds Kirke i Odense.
I Kerteminde bragte han det forfaldne skolevæsen på fode og ordnede fattigvæsenet. Der holdtes den gang i sognet gudelige forsamlinger i en lille kreds. Paludan-Müller lagde dem ikke hindringer i vejen, uagtet han kun havde lidt sympati for dem. Vel roste han de opvaktes liv, men deres hele tendens, mente han, forskruede sindene, gjorde dem tungsindige og uskikkede til livets glæde og skyldfri nydelser, medens den forledte til indbildskhed og dømmesyge. Som stiftsprovst har han ofte måttet erklære sig om forsamlingerne, og han søgte bestandig at holde middelvejen mellem for stor strenghed og slaphed. I Odense udgav han tre samlinger prædikener, som han kaldte Bidrag til Husandagt (1821-25), og hvori han søgte at give dem, der trængte til opbyggelse uden for kirkerne, en sundere føde, end de efter hans mening fik i forsamlingerne. I anledning af tusindårsfesten for kristendommens indførelse 1826 blev han indbudt til at disputere for den teologiske doktorgrad, men han afslog denne ære.
1830 kaldedes han til biskop i Århus, hvilket embede han beklædte til sin død, 14. maj 1845. Han var ingen fremtrædende biskop. Så lidt som muligt blandede han sig i de kirkelige stridigheder. Han var både som præst og videnskabsmand bange for at komme ud i, hvad der var uklart; han ville kunne se målet og vejene, der førte dertil. Friedrich Schleiermachersdogmatik syntes ham et dialektisk kunstprodukt. Læseren måtte bestandig spørge: Hvad er sandhed? Hvad er den egentlige tro? Han kan ikke tro, at Grundtvig kan nå sit mål, ikke blot fordi han bruger uforstandige midler, men også fordi "Maalet selv i sin hele Udstrækning er for gigantisk".
I politisk henseende havde han "et Horn i Siden paa Enthusiasterne", og han betragtede oprettelsen af Trykkefrihedsselskabet som et, om end godmodigt, udslag af entusiasmen. Han var også enig med Goethe i, at der aldrig taltes mere om frihed, end når det ene parti ville undertrykke de andre, og at det ikke gik ud på videre, end at magt og indflydelse skulle gå over fra den ene hånd til den anden. Men inden for den begrænsning, hvor han følte sig hjemme, stod han sikkert på sine fødder, og han gjorde et ikke ringe indtryk ved sine prædikener og endnu mere ved sin person; han forenede mildhed og overbærenhed med stor alvor. Krævede han streng pligtopfyldelse af andre, krævede han den ikke mindre af sig selv.
