Das Stadtgebiet war wahrscheinlich seit der Frühen Bronzezeit besiedelt. Nach den Völkerwanderungen errichtete im 7. Jahrhundert der slawische Stamm der Heveller gegenüber der Einmündung der Nuthe eine Burganlage an der Havel. Die erste urkundliche Erwähnung des Ortes erfolgte in einer Schenkungsurkunde des Kaisers Otto III. des Heiligen Römischen Reiches an das Stift Quedlinburg als Poztupimi am 3. Juli 993. Der Name leitet sich möglicherweise von den Wörtern Pod Stupa ab, welche mit unter den Eichen übersetzt werden können. Es liegt jedoch näher, dass sich das Wort “poztupimi” unmittelbar aus dem Mittelhochdeutschen ableitet und aus den Wörtern poz - tu - pimi gebildet worden ist. Mit den Bedeutungen ‘poz’ für zurückstoßen, ‘tu’ als Imperativ Singular des Verbs ‘tuon’ für tu! und ‘pimi’, abgeleitet von mittelhochdeutsch ‘pinen’ für zwingen, weist der Name auf eine befestigte Burgstadt nicht slawischen Ursprungs hin. Die Bedeutung der Region beruhte auf der Beherrschung des Havelübergangs.
Im Jahr 1157 eroberte Albrecht der Bär die Stadt und gründete die Mark Brandenburg. Durch Albrecht kam die Nordmark als Mark Brandenburg auch faktisch zum Heiligen Römischen Reich. Am Havelübergang wurde eine deutsche steinerne Turmburg erbaut. Im Jahr 1317 wurde die Stadt erstmals als Burg und vor allem Stadt urkundlich unter dem Namen Postamp erwähnt. 1345 erhielt Potsdam das Stadtrecht und blieb die nächsten Jahrhunderte ein kleiner städtischer Marktflecken. Von 1416 an bis zum Ende des Ersten Weltkrieges und dem damit verbundenen Untergang der Monarchie in Deutschland verblieb Potsdam im Besitz der Hohenzollern. Der verheerende Dreißigjährige Krieg und zwei Großbrände verwüsteten die Stadt.