Historia do poł. XIII w. Terytorium na którym ukształtowała się Nowa Marchia było we wczesnym średniowieczu zamieszkiwane przez plemiona słowiańskie, identyfikowane jako Pyrzyczanie na terenie Pomorza Zachodniego oraz Lubuszanie w rejonie środkowego Nadodrza. Od końca X w. znajdowało się pod rządami Polski, przy czym ustalenie zasięgu terytorialnego zdobyczy w strefie pogranicza wielkopolsko–pomorsko-lubuskiego napotyka nadal na znaczne trudności. Przyjmuje się, że Mieszko I w latach 960–972 opanował niewielki obszar na północ od ujścia Warty do Odry, niewykraczający poza obręb późniejszej kasztelani cedyńskiej, ziemi kinieckiej, ziemi kostrzyńskiej oraz regionu Santoka. Prawdopodobnie w 1005 r. (lub 1007 r.) Polska utraciła zwierzchność nad Pomorzem, w tym również nad omawianym terytorium.
Osadnictwo słowiańskie przybrało na sile od VIII w. Oprócz osad otwartych pojawiły się grody, głównie w okolicach jezior. Od IX do XI w. nastąpił rozwój osadnictwa grodowego, jednakże wskutek prowadzonych wojen pomiędzy książętami pomorskimi, wielkopolskimi i śląskimi, od XII w. na omawianym obszarze następował zanik wielu grodów i osad.