Metropolia Paderborn powstała na przełomie 1929/1930. Została erygowana po podpisaniu konkordatu przez Prusy, na mocy bulli papieża Piusa XIPastorialis officii Nostri. Powoływała ona do życia metropolię Paderborn z 3 biskupstwami w: Paderborn, Fuldzie i Hildesheim.
Po II wojnie światowej metropolia została podzielona granicą państwową NRD-RFN, co oznaczało podział istniejących diecezji w Fuldzie i Hildesheim. Wobec utrudnionych kontaktów ze wschodnimi dekanatami tej prowincji kościelnej zdecydowano się powołać w latach 60. XX wieku dwie administratury apostolskie: generalny wikariat archidiecezji Paderborn w Magdeburgu i generalny wikariat diecezji Fuldy w Erfurcie.
8 lipca 1994 miała miejsce reforma podziału terytorialnego kościoła katolickiego w Niemczech, w wyniku której odłączono od metropolii Paderborn diecezję Hildesheim na rzecz nowo powstałej metropolii Hamburga. Erygowano także na jej obszarze nowe diecezje w Magdeburgu i Erfurcie[1].