W 1518 król polski Zygmunt I Stary zezwolił Mikołajowi Działyńskiemu podkomorzemu dobrzyńskiemu i staroście brodnickiemu wykupić z rąk Mikołaja Chodzieskiego zwanego też Potulickim, wsie królewskie Budzyń, Podstolice i Brzekiniec.
W 1472 Podstolice wymienione zostały wśród wsi powiatu kcyńskiego, które nie zapłaciły wiardunków królewskich i tego powodu miały zapłacić 14 grzywien kary. W 1510 w Podstolicach było 19 łanów osiadłych, 8 łanów opustoszałych, 4 łanów opuszczonych sołectwa, dwie karczmy. W 1534 miał miejsce pobór z Podstolic o nieznanym wymiarze. W 1563 pobrano podatki od 17 łanów, a 10 łanów zwolniono z płacenia poboru z powodu pożaru. Wspomniano także dwie karczmy, kowala oraz kołodzieja.
W 1510 odnotowano we wsi 4 łany opuszczone sołectwa podstolickiego. Pobierano wówczas wiardunki dziesiętne z łanów kmiecych, które należały do biskupa poznańskiego, a meszne oraz opłata po jednym groszu z karczm plebanowi w Chodzieży. W 1565 odnotowano wiece i sądy w Podstolicach.