I middelalderen eksisterede en slavisk højborg i det nuværende Szczecinek.[2] Det var en del af den tidlige polske stat i det 10. århundrede, og som et resultat af det 12. århundredes fragmentering af Polen blev det en del af det separate Hertugdømmet Pommern.
I 1310 blev slottet på stedet for en tidligere højborg og by grundlagt under Lübeck lov af hertug Wartislaw 4. af Pommern og modelleret efter Szczecin, som ligger ca. 150 km mod vest. I 1707 var byen kendt på polsk som Nowoszczecin, mens Mały Szczecin-navnet gradvist udviklede sig til det moderne navn Szczecinek.[3]