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 Schloß Neuhaus in 1973. The Paderborn club was founded in 1908 as FC Preußen Paderborn which became VfJ 08 Paderborn in 1920 and was merged with another local side SV 13 Paderborn to become FC Paderborn in 1968. 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.
A series of steadily improved finishes in the Regionalliga Nord (III) led to Paderborn advancing to second tier play in 2005. They spent most of the following decade as a lower table side in the 2. Bundesliga before breaking through in their 2013–14 campaign. A 2–1 victory at home over Aalen on 11 May 2014 secured a second place finish and promotion to the 1. Bundesliga for the first time in the club's history.