มหาวิหารในปัจจุบันตั้งอยู่ในทำเลที่เคยเป็นที่ตั้งของโบสถ์มานานหลายร้อยปีชาร์เลมาญทรง สร้าง พระราชวังไกเซอร์ฟัลซ์ใกล้กับต้นกำเนิดของแม่น้ำพาเดอร์ตั้งแต่ปี 777 พระราชวังแห่งนี้มีโบสถ์ติดอยู่ด้วย ซึ่งอุทิศให้กับพระคริสต์ (Salvator Mundi) และบริกิตแห่งคิลแดร์โบสถ์แห่งนี้ตั้งอยู่ทางเหนือของมหาวิหารในปัจจุบัน ทำหน้าที่เป็นโบสถ์น้อยประจำราชสำนักและเป็นฐานสำหรับการเผยแพร่ศาสนาในหมู่ชาวแซกซอนที่นับถือศาสนาอื่น ชาวแซกซอนที่ก่อกบฏได้ทำลายโบสถ์แห่งแรกนี้ซ้ำแล้วซ้ำเล่า หลังจากที่ชาวบ้านเปลี่ยนมานับถือศาสนาคริสต์ มหาวิหารแห่งแรกจึงถูกสร้างขึ้นสมเด็จพระสันตะปาปาเลโอที่ 3 ทรง พบกับชาร์เลมาญที่พาเดอร์บอร์นในปี 799 และทรงประกอบพิธีอุทิศแท่นบูชาแด่นักบุญสตีเฟน พร้อมทั้งประดิษฐานพระธาตุของนักบุญองค์นั้นไว้ในนั้น มหาวิหารแห่งแรกของสังฆมณฑลที่จัดตั้งขึ้นใหม่เป็น มหาวิหารแบบสามทางเดิน อุทิศให้กับพระแม่มารีและนักบุญคิเลียนหลังจากที่การปกครองส่วนภูมิภาคเริ่มต้นจากเมืองเวือร์ซบูร์กในปี 806 ฮาธูมาร์ได้เป็นบิชอปองค์แรกของพาเดอร์บอร์น^{[ 1 ] : 8–9}

บิชอปองค์ที่สองบาดูราดได้ขออัฐิของนักบุญจากบิชอปแห่งเลอ ม็องเพื่อช่วยเสริมสร้างความศรัทธาของชาวแซกซอนในท้องถิ่น ในปี 836 อัฐิของลิโบเรียสแห่งเลอ ม็องได้ถูกส่งมอบให้กับคณะผู้แทนจากพาเดอร์บอร์น และเคลื่อนย้ายกลับไปยังมหาวิหาร มหาวิหารแห่งแรกถูกทำลายด้วยไฟไหม้ในปี 1000 บิชอปราเธริอุสเริ่มสร้างใหม่ แต่ผู้สืบทอดตำแหน่งของเขาไมน์เวิ ร์ก ได้ทำลายสิ่งก่อสร้างเดิมและเริ่มต้นใหม่ โดยสร้างโบสถ์สามทางเดินที่มีปีกโบสถ์และห้องใต้ดินทางทิศตะวันออก มหาวิหาร (แห่งที่สอง) นี้ได้รับการถวายในปี 1015 แต่ถูกทำลายด้วยไฟไหม้ในเมืองในปี 1058 หลานชายของไมน์เวิร์กอิมัดได้สร้างมหาวิหารขึ้นใหม่ในขนาดที่ใหญ่ขึ้นอย่างมาก (มหาวิหารแห่งที่สาม) อาคารนี้มีปีกโบสถ์สองแห่ง ซึ่งคล้ายกับมหาวิหารในปัจจุบันมาก ห้องใต้ดินในปัจจุบันสร้างขึ้นประมาณปี 1100 ในทำนองเดียวกัน โบสถ์น้อยของนักบุญบาร์โธโลมิวซึ่งเชื่อมต่อกับมหาวิหาร^{[ 2 ]}จะถูกสร้างขึ้นหลังปี 1015 โดยพระสงฆ์ชาวกรีก^{[ 3 ]} ไฟไหม้อีกครั้งในปี 1133 ทำให้โบสถ์เสียหาย แต่ส่วนแกนกลางยังคงอยู่รอด เบอร์นาร์ดที่ 1 ฟอน โอเซเดได้ทำการเสริมความแข็งแรงและขยายอาคาร (มหาวิหารแห่งที่สี่) และได้รับการถวายใหม่ในปี 1144/45 ^{[ 1 ] : 9}

ในศตวรรษที่ 13 มหาวิหารได้รับการบูรณะใหม่ ไม่ใช่เพราะความเสียหาย แต่เพื่อให้สอดคล้องกับมาตรฐานทางศิลปะและศาสนจักรในยุคนั้น การก่อสร้างน่าจะเริ่มต้นที่ปลายด้านตะวันตกของอาคาร ( แบบบาซิลิกา โรมาเน สก์ตอนปลาย ก่อนปี 1220) ส่วนของทางเดินกลางสร้างตามแบบโบสถ์โถง (เช่น มีทางเดินสามทางที่สูงเท่ากับหลังคาตรงกลาง) ในรูปแบบโกธิก ตอนต้น สร้างเสร็จสมบูรณ์ในช่วงปลายศตวรรษที่ 13 โดยมีองค์ประกอบแบบโกธิกชั้นสูง^{[ 1 ] : 11}

ในศตวรรษที่ 17 เจ้าชาย-บิชอปดีทริชอดอล์ฟ ฟอน เดอร์ เรคเคอ (1601-1661) และเฟอร์ดินันด์ ฟอน เฟิร์สเตนแบร์ก (1626-1683) ได้เปลี่ยนลักษณะภายในแบบโกธิกด้วยงานศิลปะสไตล์บาโรก^{[ 1 ] : 11}

ในปี พ.ศ. 2473 เขตปกครองของแพเดอร์บอร์นได้รับการยกฐานะเป็นอัครสังฆมณฑล^{[ 1 ] : 13}

การทิ้งระเบิดซ้ำแล้วซ้ำเล่าของฝ่ายสัมพันธมิตรที่เมืองพาเดอร์บอร์นในปี พ.ศ. 2488 ส่งผลให้มหาวิหารได้รับความเสียหายอย่างหนักและสูญเสียผลงานศิลปะอันล้ำค่าที่หาทดแทนไม่ได้ รวมถึงหน้าต่างกระจกประวัติศาสตร์ทั้งหมด^{[ 1 ] : 13} เมื่อวันที่ 22 มีนาคม พ.ศ. 2488 มีผู้เสียชีวิต 14 คนจากระเบิดขนาดใหญ่ในบริเวณระเบียงทางเดิน^{[ 1 ] : 36}

การบูรณะใช้เวลานานจนถึงทศวรรษ 1950 ระหว่างปี 1978 ถึง 1981 ได้มีการบูรณะครั้งใหญ่^{[ 1 ] : 13}

• ความยาว: 104 เมตร
• ความกว้าง: 52 เมตร
• ความสูง: 28 เมตร
• ความสูงของหอคอยด้านตะวันตก: 93 ม. ^{[ 1 ] : 13}

• ประตูสวรรค์ (Paradise Portal) สร้างขึ้นในช่วงหนึ่งในสามแรกของศตวรรษที่ 13 ผสมผสานประติมากรรมแบบโรมาเนสก์ตอนปลายและโกธิกตอนต้น^{[ 1 ] : 15}
• Pietàจากราวปี ค.ศ. 1360 น่าจะทำในเฮสเซ^{[ 1 ] : 23–4}
• ภาพนูนต่ำทำจากหินอะลาบาสเตอร์แสดงการเคารพสักการะเหล่าโหราจารย์สร้างขึ้นในนอตติงแฮมราว ปีค.ศ. 1360 ^{[ 1 ] : 24}
• Doppelmadonna (พระแม่มารีคู่) แขวนจากเพดานในโบสถ์ จากประมาณปี ค.ศ. 1480 ^{[ 1 ] : 23}
• แท่นบูชา Reliquienrentabel ซึ่งเป็นแท่นบูชาหลัก แบบโกธิกเดิม(สร้างขึ้นราวปี ค.ศ. 1420 จากหินทรายสีอ่อน และออกแบบมาเพื่อประดิษฐานหีบเก็บพระธาตุของนักบุญลิโบรี ซึ่งถูกขโมยไปในช่วงสงครามสามสิบปี ) ถูกแทนที่ด้วยแท่นบูชาหลักแบบบาโรกในศตวรรษที่ 17 (ถูกทำลายในปี ค.ศ. 1945) ปัจจุบันแท่นบูชานี้กลับมาตั้งอยู่ในบริเวณร้องเพลงประสานเสียงของมหาวิหารอีกครั้ง^{[ 1 ] : 25–6}
• สุสานของบิชอปโรโธ (ดำรงตำแหน่งระหว่างปี 1036–51) ประมาณปี 1460 ^{[ 1 ] : 31}
• แท่นบูชามาร์กาเรเธนัลทารีแท่นบูชาไม้สมัยกลางที่ยังคงเหลืออยู่เพียงแห่งเดียววาดโดยเกิร์ต ฟาน ลูน (ประมาณ ค.ศ. 1465–1521) ^{[ 1 ] : 17}
• สุสานของเจ้าชายบิชอปดีทริชที่ 4 แห่งเฟือร์สเตนเบิร์ก (เสียชีวิต ค.ศ. 1618) ผลงาน ศิลปะแบบแมนเนอริสต์ที่ทำจากหินสีดำและสีขาว สูงเกือบ 18 เมตร^{[ 1 ] : 19}
• แท่นเทศน์สไตล์เรฌ็องซ์ สีขาวและทอง (ค.ศ. 1736) มอบให้เนื่องในโอกาสครบรอบ 900 ปีแห่งการย้ายนักบุญลิโบเรียส^{[ 1 ] : 23}
• อ่างล้างบาปมีอายุตั้งแต่ปี 1924 เท่านั้น แต่ฉากกั้นแบบแมนเนอริสต์ที่ล้อมรอบนั้นมาจากศตวรรษที่ 17 ^{[ 1 ] : 17}

พระธาตุ ของนักบุญลิโบเรียสถูกเก็บรักษาไว้ใน ห้องใต้ดินสามทางเดินซึ่ง (มีความยาว 32  เมตร) เป็นหนึ่งในห้องใต้ดินที่ใหญ่ที่สุดของเยอรมนี ทางด้านทิศตะวันตกเป็นที่ตั้งของสุสานของอาร์คบิชอปแห่งพาเดอร์บอร์น ห้องโถงมีภาพโมเสกปี 1935 บนผนังและเพดาน และตรงกลางพื้นมีศิลาจารึกหลุมศพของบิชอปไมน์เวิร์ก ซึ่งมีอายุย้อนไปถึงศตวรรษที่ 13 ^{[ 1 ] : 29}

หนึ่งในจุดเด่นที่รู้จักกันดีที่สุดของมหาวิหารและของเมืองคือ"หน้าต่างกระต่ายสามตัว" ( Dreihasenfenster ) ซึ่งแสดงภาพ กระต่ายสามตัวกำลังเคลื่อนไหวเรียงกันเป็นรูปสามเหลี่ยม โดยกระต่ายแต่ละตัวมีหูสองข้าง แม้ว่าในความเป็นจริงจะมองเห็นเพียงสามหูเท่านั้น ภาพแกะสลักดั้งเดิมในศตวรรษที่ 16 สามารถพบได้ใน ลานภายในของ อารามและมีการจำลองแบบไว้บนอาคารและร้านค้าหลายแห่งทั่วใจกลางเมือง