Pierwsza wzmianka o Paterku pochodzi z datowanego na 1720 dokumentu, w którym August II Mocny potwierdził przywileje Nakła. Ignacy Geppert w Dziejach ziemi nakielskiej wymienia istniejące na terenie dzisiejszego Paterka 3 miejscowości: Paterek Miejski, Paterek Wiejski i Paterek Dworski. Paterek Miejski został ok. 1870 na prośbę mieszkańców wyłączony z Nakła. Słownik geograficzny Królestwa Polskiego i innych krajów słowiańskich wspomina 2 miejscowości:
Paterek (niem. Paterke, Steinburg), w której mieszkało 197 osób (167 protestantów oraz 30 katolików)
Paterek Miejski (niem. Paterke, Brückenkopf) – 856 mieszkańców (447 protestantów, 304 katolików i 5 judaistów).
Podczas Powstania wielkopolskiego na terenie Paterka stoczono kilka potyczek. Największa z nich rozegrała się 7 lutego 1919. Z tego okresu pochodzi grób powstańca znajdujący się do dzisiaj na miejscowym cmentarzu.
W 1945 oddziały niemieckiej żandarmerii rozstrzelały w Paterku 250 Polaków i Żydów, przywiezionych z następujących miejscowości: Nakło, Glesno, Józefina, Kościerzyn Wielki, Kruszki, Mrocza, Pobórka Wielka, Podgórze, Ruda, Wiktorówko, Wyrzysk i Wysoka Krajeńska. Wśród ofiar znalazło się 3 dzieci i 15 kobiet.
Na terenie wsi zlokalizowane są dwa nieczynne cmentarze ewangelickie.