The club was formed out of the 1985 merger of FC Paderborn and TuS Schloß Neuhaus as TuS Paderborn-Neuhaus and took on its current, shorter name in 1997. The Neuhaus club was founded in 1907 as SV 07 Neuhaus which was joined by the local side TuS 1910 Sennelager to become TuS Schloss Neuhaus in 1970. The Neuhaus and Paderborn teams played as tier III sides for most of their histories, as has the unified club. Today Paderborn plays its home matches at the Benteler Arena.
The club is known for its involvement in a notorious DFB-Pokal contest played against Bundesliga side Hamburger SV on 21 August 2004. Paderborn upset HSV 4–2 and it was revealed in January 2005 that the match referee, Robert Hoyzer, had taken money from Croatian gambling syndicates to fix the match using two wrongly awarded penalties and a questionable red card. It soon developed that the game was only one of a number in which game officials, coaches, and players accepted payment to influence the outcome. The resulting scandal was to become the biggest in German football in over thirty years, and was a major embarrassment to the country during its preparations to host the 2006 FIFA World Cup.
Paderborn finally finished 2. Bundesliga as 2nd after defeating 2-1 Aalen at home match in 11 May 2014 and was promoted to the 1. Bundesliga for the first time in club history.