В названии «Падерборна 07» стоит 1907 год, но история клуба намного сложнее, чем подсказывает эта цифра. Точкой отсчёта считается 14 августа 1907 года, когда группа из двадцати друзей основала в районе Нойхаус клуб «Арминия Нойхаус». Нынешний «Падерборн» вырос из нескольких местных традиций, а непосредственно из слияния 1985 года, когда «ТуС Шлосс-Нойхаус» объединился с «1. ФК Падерборн», образовав «ТуС Падерборн-Нойхаус». В 1997 году клуб принял нынешнее название, в котором «07» отсылает к дате основания «Арминии». Клубные цвета: синий, белый и чёрный.
Новая команда начинала на третьем уровне и, если не считать сезон 2000/01, проведённый на четвёртом уровне из-за реорганизации лиг, долго оставалась там. Во второй дивизион клуб поднялся лишь в 2005 году, после двадцати лет упорного восхождения. «Падерборн» к тому же не классическая футбольная метрополия: в городе без давней футбольной традиции клубу пришлось с нуля создавать и организацию, и круг болельщиков. Капитан Маркус Крёше позже вспоминал, что, когда он пришёл в 2001 году, на стадионе имени Германа Лёнса его матчи смотрели лишь шестьсот зрителей.
Переломным стал сезон 2013/14, когда под руководством Андре Брайтенрайтера «Падерборн» впервые в истории пробился в Бундеслигу. Решающая победа 2:1 над «Аленом» закрепила этот успех в последнем туре. Новичка считали одним из главных кандидатов на вылет, но после трёх побед в начале сезона 2014/15, включая 3:0 в Гамбурге и 2:0 над «Ганновером», он возглавил таблицу после четырёх туров. С этим матчем 20 сентября 2014 года связан и гол Морица Штоппелькампа с расстояния 82,3 метра, самый дальний в истории Бундеслиги, забитый при полных трибунах на 15 тысяч зрителей. Приключение, однако, закончилось вылетом с восемнадцатого места, а год спустя «Падерборн» занял последнее место во втором дивизионе и вылетел во второй раз подряд.
Следующие годы принесли восстановление. Под руководством Штеффена Баумгарта клуб дважды подряд выходил в классе и в 2019 году вернулся в Бундеслигу. Сезон 2019/20, правда, завершился так же, как и первый: восемнадцатое место и вылет. История «Падерборна» — это история клуба, который не раз возвращался туда, где его никто не ждал, не располагая ресурсами крупнейших соперников, и сделал честолюбивую атакующую игру своей визитной карточкой.
Идентичность клуба держится на сообществе, выросшем вместе с ним. Та же арена, что когда-то собирала несколько сотен зрителей, в годы элиты заполнялась до последнего места, а болельщики сопровождали команду через вылеты и возвращения. Для многих из них символом клуба остаётся старая скромная арена с линиями электропередачи над трибунами.
Этот символ — стадион имени Германа Лёнса, открытый в 1957 году и использовавшийся «Падерборном» до 2008 года. Затем клуб переехал на современную арену, вмещающую чуть более 15 тысяч зрителей, построенную в 2005–2008 годах примерно за 25 миллионов евро и расширенную перед выходом 2019 года. Как и весь клуб, стадион прошёл путь от скромного поля района Нойхаус до арены, где играли «Боруссия» Дортмунд и «Бавария», а его коммерческое название с годами менялось. Регион Падерборна на востоке Северного Рейна — Вестфалии получил клуб, который по-прежнему показывает, что в футболе можно пройти путь от любительских полей до Бундеслиги, не потеряв собственного характера.