Pod koniec I tysiąclecia Pałuki miało zamieszkiwać plemię Pałuczan, które podporządkowało się Polanom. W tym też czasie przewodnią rolę od Biskupina przejęło zapewne Łekno, które było stolicą kasztelanii (jak podaje Bulla gnieźnieńska z 1136). W 1227 w Gąsawie miał miejsce słynny zjazd książąt polskich, na którym zamordowano ostatniego seniora, Leszka Białego. W tym też czasie lokowano Kcynię oraz Żnin, które stały się kasztelaniami. W 1314 Pałuki znalazły się w granicach Polski odrodzonej po rozbiciu dzielnicowym. Za Kazimierza Wielkiego rozwijały się prężnie i zyskiwały mieszkańców – prawa miejskie uzyskały wtedy Gołańcz, Szubin i Wenecja.