Bereits in der Bronzezeit besiedelten indogermanische Stämme auf einzelnen Schwemmsandinseln das Oderbruch. In Alt-Drewitz wurden bei Ausgrabungen Dolchklingen aus der Frühbronzezeit (2000-1400 v.Chr.) gefunden. Ein Friedhof aus der Lausitzer Kultur wurde in der Neustadt, östlich der Pionierkaserne entdeckt. Man vermutet die dazugehörigen Dörfer weiter südlich, am Höhenrand des Warthebruchs. Im Küstriner Ortsteil Lagardesmühlen wurde eine germanische Siedlungen aus dem 1.Jh. ausgegraben. Gefunden wurden Herdstellen, Pfostenlöcher, Scherben sowie ein Stempel mit lateinischen Buchstaben auf einem Gefäß. Ein Urnengräberfeld aus der gleichen Zeit wurde westlich, in der Weinberg- und Schiffbauerstraße entdeckt.
Die Semnonen, ein Zweigstamm der elbgermanischen Sueben, siedelte vor 2000 Jahren am Oderbruch und errichteten vermutlich auch südlich von Küstrin, auf dem nahegelegenden Reitweiner Sporn eine Wallanlage. Ab dem 3. Jahrhundert verließen die Semnonen, bis auf wenige Restgruppen ihre Heimat zwischen Havel und Oder in Richtung Oberrhein und schlossen sich den Alemannen, den späteren Schwaben an. Die in Brandenburg verbliebenen Reste gingen im 6./7. Jahrhundert in den Slawen auf, welche im Zuge der Völkerwanderung das Gebiet besiedelten. Ein slawisches Dorf wurde Ende des 19.Jh. auf dem Gelände der Pionierkaserne ausgegraben. Der Befund deutet auf eine Nutzung bis ins 13.Jh hinein.

Flüsse dienten von altersher als Handels- und Transportwege. Zwischen den Hochflächen im Norden und Süden bot sich hier, am Kreuzungspunkt von Warthe und Oder, ein Übergang zu den Hochflächen des Oder/Warthebruchs an. Eine große Insel, die Stätte der späteren Stadt, ermöglichte einen Halt. Von hier aus überschritt man die Wasserläufe. Ein Fischerdorf befand sich ursprünglich auf dieser Insel im Winkel zwischen Oder und Warthe in der Nähe des Flußübergangs, ungefähr dort, wo heute der Kreisverkehr die Straße nach Frankfurt/O und Sonnenburg (Slonsk) teilt.
Ende des 10.Jh beherrschten die Pommern das Gebiet. Das pommersche "kosterin" bezeichnet einen Ort, an dem viel Borstenhirse wächst. Oder und Warthe bildeten wohl die Grenze zu Polen und so hatte dieser Oderübergang einen besonderen strategischen Wert. Zu seinem Schutz legten die Pommern ein festes Haus an - ein niedriger Turm mit Fachwerkaufbau und einer Palisadenumwallung. Es ist davon auszugehen, daß im Bereich des heutigen Fischertores eine Zollbude errichtet und Wegezoll für die Oderüberquerung erhoben wurde.
Die Polanen unter Boleslav I. (992-1025) eroberten im Jahr 995 Pommern östlich der Oder, doch konnten die Pommern zwischen 1005 und 1013 ihre Unabhängigkeit wiedererlangen. Nach einigen Rückschlägen stellte Boleslav Schiefmund (1107-1138) die polnische Herrschaft wieder her. Da das Gebiet weiterhin hart umkämpft blieb, übertrug 1232 der erfolglos regierende Herzog Boleslav V. (1227-1279) das Gebiet den Tempelrittern, mit dem Recht ein Forum (Markt) nach deutschen Recht zu errichten. Der Bischof von Lebus erließ ihnen den Zehnten.

Der neue Markt wurde in bester Verkehrslage nördlich des Oderübergangs neben der Oderbefestigung in der für Kolonialstädte üblichen Form angelegt. Von jeder Ecke des Marktes gingen zwei Straßen ab. Die westliche Längstseite wurde von einer Quergasse durchschnitten, die zur Schloßfreiheit führte. Die östliche Straße blieb ungeteilt, was beweist, daß diese frühe Anlage nur den Marktplatz umfasste. Ursprünglich umsäumten Wohnhäuser den Markt, erbaut in Fachwerk mit dem Giebel zur Straße . Hinter der Westfront des Marktes begann die Schloßfreiheit auf der man die 1232 die Kirche und Pfarrhaus erbaut hatte. Das alte slawische Dorf "Küstrin" wurde nun Kietz genannt und nach Osten abgedrängt. Vermutlich gründen sich die Häuser der Kietzer Straße auf den Resten des slawischen Dorfes, was durch entsprechende Grabungsbefunde zu beweisen wäre. Der deutsche Marktplatz und der Kietz waren zuerst noch durch einen Landstreifen getrennt, wuchsen jedoch allmählich zusammen.

Von 1261 an gehörte Küstrin zur Markgrafschaft Brandenburg, als die Askanier ihre Besitzungen in Lebus und Landsberg a.d. Warthe verbanden. In der Abtretung der Templer wird Küstrin jedoch nicht namentlich sondern lediglich als "Oppidum" (kleine befestigte Stadt) erwähnt, wobei als "befestigt" nur das feste Haus der Pommern gemeint sein kann. Um 1300 wird von einer Stadt berichtet, welche vormals Hohen-Küstrin genannt wurde, die ihre Stadtgerechtigkeit nebst niederen Gerichten behaupten kann. Das Magdeburger Stadtrecht erhielt Küstrin durch Albrecht III. v. Brandenburg, der die Städte in der Mark Brandenburg besonders förderte. Das Stadtwappen mit dem Fisch und dem halben brandenburgischen Adler ist seit dem Jahr 1364, zuerst auf einem Siegel, nachweisbar. Als das Geschlecht der Askanier 1319 erlosch, war Küstrin herrenlos und wechselte mehrfach den Besitzer. 1323 kam es an die wittelsbacher Linie Brandenburgs und war 1398 an den Johanniter-Orden verpfändet.

Der Deutsche Orden übernahm ab 1402 das Pfand an der Stadt und so wurde Küstrin nun Sitz des Ordensvogtes der Neumark und sicherte die Verbindung zwischen dem Ordensland im Osten und dem Westen des Deutschen Reiches. Gefahr drohte der Stadt jedoch weniger vom durch innere Machtkämpfe zerstrittenen polnischen Adel, als von Brandenburg, da 1425 die Ambitionen des befreundeten brandenburgischen Kürfürsten bekannt wurden. Küstrin wurde nicht von Mauern oder Wällen umgeben, allein die Flüsse und das sumpfige Gelände schützten die Stadt. 1446 erteilte der Hochmeister der Stadt den Befehl, einen Palisadenzaun um die Stadt zu errichten.
Weitere Planungen sahen vor, das pommersche feste Haus ab 1440 zu einer kastelförmigen Burg auszubauen. Dem Stand der Waffentechnik folgend, sollten an den Eckpunkten des Kastells Rundbastionen oder niedrige Türme entstehen.

Dem Stand der Waffentechnik folgend, sollten an den Eckpunkten des Kastells Rundbastionen oder niedrige Türme entstehen. Es sind jedoch keine Bauunterlagen dieser Ordensburg erhalten. Dennoch kann man davon ausgehen, daß der Entwurf typisch für die Ordensburgen in Preußen gewesen ist und der Ordensburg in Rehden sehr ähnelte. Der Bau wurde jedoch aus Geldmangel zunehmend reduziert und immer wieder verzögert. Daher standen ein Neubau auf der Westseite und das alte pommersche feste Haus noch längere Zeit nebeneinander.
1447 wird mit Grundsteinlegung von 2 Türmen begonnen von denen nur ein Turm 1452 vollendet werden kann. Vermutlich handelt es sich bei diesem Turm um den Bergfried, dessen Bau bereits 1444 vom Baumeister empfohlen wurde, um die Zugbrücke an der Oderseite besser zu schützen. Ebenfalls wird 1452 die Grundsteinlegung des Remter und der Küche bestätigt, welche im Laufe des Jahres auf anderthalb Zimmerhöhe aufgemauert wurden. Vollendet dürfte der Schloßbau allerdings erst nach 1455 sein. Der Versuch, eine Zwingermauer um die Burg zu errichten, scheiterte am hohen Grundwasserspiegel. So wurde aus der Baugrube ein das Schloß umgebener Wassergraben und der eigentliche Wassergraben wieder zugeschüttet. Ebenfalls wird 1452 die Grundsteinlegung des Remter und der Küche bestätigt, welche im Laufe des Jahres auf anderthalb Zimmerhöhe aufgemauert wurden. Vollendet dürfte der Schloßbau allerdings erst nach 1455 sein.
Als 1454 der letzte Krieg des Deutschen Ordens gegen Polen begann, wurden in Küstrin 2000 Landsknechte rekrutiert, die in der Schlacht bei Konitz erfolgreich kämpften.
Der durch den Krieg finanziell angeschlagene Deutsche Orden verkaufte die Neumark 1455 wieder an den Kurfürsten Friedrich II. von Brandenburg. Friedrich übergab 1470 nach erfolglosen Kämpfen gegen die Pommern, in denen er die besetzte Uckermark nur teilweise zurückerobern konnte, die Herrschaft seinem Bruder Albrecht Achilles. Zu dieser Zeit war Albrecht von Brandenburg (1414 - 1486) als Albrecht I. ,Markgraf von Ansbach und Kulmbach, sowie später als Albrecht III., der dritte Kurfürst von Brandenburg aus dem Hause Hohenzollern.
1492 zerstört ein Großbrand die gesamte Stadt. Kurfürst Joachim gewährt daraufhin den Küstriner Bürger für 4 Jahre Steuerfreiheit. Doch konnte sich die Stadt nur langsam von dem Unglück erholen. Die Häuser wurden entlang der alten Straßenzüge wieder aufgebaut. Die Straßen blieben ohne Pflaster und die Häuser wurden mit Stroh oder Holzschindeln gedeckt. So blieb die Feuergefahr trotz eines Feuerganges zwischen den Häusern bestehen.