Klub berdiri pada tahun 1985 dari hasil merger dua klub, yaitu FC Paderborn dan TuS Schloß Neuhaus sebagai TuS Paderborn-Neuhaus. Klub Neuhaus berdiri pada tahun 1907 sebagai SV 07 Neuhuas dan bergabung dengan klub lokal lainnya, TuS 1910 Sennelager dan berubah nama menjadi TuS Schloss Neuhaus pada tahun 1970. Klub Neuhaus dan Paderborn bermain di Divisi Tiga pada sebagian besar perjalanan sejarah mereka.
Klub bermarkas di Benteler Arena yang berkapasitas 15.000 penonton.
Klub pun ikut terseret kasus Skandal pada tahun 2004 di ajang Piala Jerman saat mereka berhasil mengalahkan Hamburger SV 4-2. Ini terungkap pada Januari 2005, saat wasit pada pertandingan itu, Robert Hoyzer, diketahui telah menerima uang sogok dari sindikat Judi asal Kroasia untuk memberikan dua hadiah penalti dan satu kartu merah. Dan setelah diselidiki lebih lanjut, laga ini, hanyalah satu dari sekian banyak laga yang telah diatur, dan pelatih, pemain, dan perangkat pertandinga menerima uang sogok sebagai pelicin. Skandal ini, merupakan yang terbesar dalam 30 tahun, dan ikut mempengaruhi persiapan Jerman yang akan menjadi tuan rumah Piala Dunia pada tahun berikutnya. Pada perhelatan Divisi dua Bundesliga musim 2013-14, mereka mengakhiri musim di posisi kedua atau runner-up, setelah berhasil mengalahkan VfR Aalen dengan skor 2-1 pada pertandingan home pada 11 Mei 2014 dan berhasil promosi ke Bundesliga untuk pertama kalinya dalam sejarah klub.
