Unmittelbar nach Beendigung des Schloßbaus, begann 1537 der Festungsbau in altniederländischer Manier. Einen ersten Plan der Festung entwarf schon 1535 der Ingenieur Maurer mit fünf Bastionen und Kavalieren, jedoch noch ohne Raveline. Die Festung hatte in der Planung keine größere geostrategische Bedeutung, sondern diente vorrangig dem Schutz des Markgrafen und dessen Angehörigen. So blieb der Festung nur die Aufgabe den Oderübergang zu sperren. Weitergehende strategischen Ziele konnten infolge der geringen Ausdehnung der Festung erst im späten 19.Jh verfolgt werden, als die Vorfeldbefestigung in einen Radius von rund 10 km ausgebaut wurden.
Die Stadt erhielt zunächst einen Gürtel von hohen Erdwällen und Gräben, deren Flanken von rechteckigen, gemauerten Basteien geschützt wurden, die schon damals militärisch überholt waren. Bis zu ihrer jetzigen Gestaltung wurden die Bastionen im 16.Jh mehrfach umgestaltet und erweitert. Über den Grund kann nur noch spekuliert werden, da keine Projektierungsunterlagen erhalten geblieben sind. In den erhalten gebliebenen Bastionen König und Phillip kann diese Entwicklung sehr gut nachvollzogen werden. Nach sechs Jahren Bauzeit wurde diese erste Besfestigung fertiggestellt.
1543 konnten die schweren Geschütze aus Königsberg und Cottbus in der Festung aufgestellt werden. Da Hochwasser regelmäßig die Wälle beschädigte, ließ Markgraf Johann 1553, mit Zustimmung der neumärkischen Stände, die Festungswälle mit Steinmauern errichten. Die Bauleitung übernahm ab 1562 der italienische Festungsingenieur Giromella, mit dessen Verpflichtung genau der richtige Mann für dieses ehrgeizige Projekt gefunden wurde, denn der Bau im morastigen Untergrund am Oderufer erwies sich als sehr aufwendig und teuer.

Da der vorhandene Flußsand als Baugrund nicht ausreichte, um derartige massive Bauwerke zu errichten, mußten zunächst Eichenstämme kastenförmig in den sumpfigen Boden getrieben werden, damit das Fundament nicht versank. In diesen Kasten von etwa 2 Metern Kantenlänge wurden Eichen - und Kiefernstämme in den Untergrund gerammt. Dieser Vorgang wurde im Abstand von ca. zwei Metern für den gesamten Fundamentbereich wiederholt. Auf diesen Holzkästen erfolgte die Aufmauerung. Die einzelnen Kästen wurden mit Mauerbögen verbunden. Erst dann konnte ein massiver Mauerverband gebildet werden.
Die Umwallung der Festung wurde unter Johann von Küstrin nur vorläufig beendet und unter seinen Nachfolgern Johann Georg (1571-1598) weitergeführt. Graf Rochus zu Lynar, Nachfolger Giromellas, war seit 1579 in Küstrin tätig.

Der älteste erhaltene Plan der Festung geht vermutlich auf ihn zurück. Dieser Plan enthält bereits die erst 200 Jahre später ausgeführte Bastion Brandenburg. Auffällig ist die unterschiedliche Detailierung der Festungsbauten in diesem Plan. Es ist anzunehmen, daß dieser Plan bereits ausgeführte Festwerke darstellt, sowie Bauwerke aufführt, die sich noch in der Bauphase befinden. Vermutlich kam es während der Bauausführung wegen des schwierigen Baugrunds häufig zu Änderungen gegenüber dem ursprünglichen Bauplan . 1574 wurden noch Arbeiten an den Wällen ausgeführt, 1580 und 1586 sind Arbeiten am Gohrintor (später Berliner Tor genannt) und nach dem alten Kietz nachgewiesen, da die Festung an dieser Stelle noch zu offen war. 1584 stürzten infolge des starken Oderhochwassers Teile der Bastion König ein. Die Umfangreiche Pfahlgründungen zogen sich bis 1586 hin, ehe die eigentlichen Maurerarbeiten beginnen konnten.

Erst 1588 konnte der Umbau der altertümlichen Bastei zu einer Bastion nach italienischen Vorbild abgeschlossen werden. Die bisherigen Schießscharten an der Nord- und Westseite wurden verschlossen. Bei den Restaurierungsarbeiten im 21.Jh wurden an den verbliebenen Bastionen Phillip und König deutliche Baumängel festgestellt, die teilweise auf eine nachlässige Bauausführung in der Entstehungzeit zurück zuführen sind. Die im 16.Jh verwendeten Ziegel wurden von Ziegeleien aus der näheren Umgebung gefertigt, enthielten viel Mergel und waren insgesamt von schlechter Qualität.
Mit geringen Aufwand wurden Bauarbeiten unter Joachim Friedrich ( -1608) und Johann Sigismund (-1619) weitergeführt. So entstanden unter Joachim Friedrich zur Deckung des Weges zur kurze Vorstadt, der späteren Neustadt, zwei Schanzen, die späteren Redans 7 und 8. Weiterhin wurden Einpfählungen an der Uferseite vorgenommen, um ein unterspülen der Festungsmauer einzudämmen.
1546 ordnete Markgraf Hans eine Festungsbesatzung von 300-400 Landsknechten mit einer monatlichen Besoldung von 4 Gulden an. Jedoch war diese Summen nicht aufzubringen uns so wurde die Festungsbesatzung auf 150 Mann reduziert. 1621 standen 160 Mann unter Sold. Kasernen waren unbekannt, die Einquartierung der Soldaten erfolgte durch die Stadtbevölkerung, wodurch sich die Raumnot innerhalb der Stadt noch verschärft. Eine 1599 beim Kurfürsten einhobene Klage brachte keinen Erfolg. War die Festungsbesatzung nicht aktiv in Kampfhandlungen einbezogen worden, so wurde doch streng auf die Aufrechterhaltung der Disziplin geachtet und Verstöße streng, bis hin zur Todesstrafe bestraft. Prügeleien und Alkoholmißbrauch waren verboten. Während der dienstfreien Zeit durfte der Landsknecht sich nur einen Gewehrschuß weit von den Festungsanlagen entfernen. 1630 als die Kriegshandlungen auch die protestantische Mark bedrohten, wurde die Festungsbesatzung aufgelöst und durch Kompanien der Feldarmee ersetzt.
1604 wurde der Durchgangsverkehr durch die Festung gestattet. Das Gohrintor wurde zum langen Dammtor und des letzte Stück des kurzen Damms verbreitert. An der Stelle wo vom Damm der Weg um die Stadt führt wurde vermutlich auch in dieser Zeit die kleine Schanze vor dem Hohen Kavalier errichtet. Die Schanze stellt das einzigste Außenwerk vor 1631 dar.

Panoramaansicht Küstrins um 1650 aus westlicher Richtung - Merians Darstellung basiert auf einer rund 50 Jahre älteren Handskizze, die auch die Grundlage für weitere Darstellungen war

Panoramaansicht Küstrins um 1650 aus westlicher Richtung - Merians Darstellung basiert auf einer rund 50 Jahre älteren Handskizze, die auch die Grundlage für weitere Darstellungen war

Der 30jährige Kriege machte eine Modernisierung der Festung erforderlich. In der Zeit der schwedischen Besatzung wurden 1631 die Raveline am Kietzer Tor und dem Gohrintor (später Berliner Tor) gebaut. Zum Schutz der Oderbrücke wurde zunächst ein Ravelin errichtet, der später zu einer zur Festung hin offenen Erdschanze mit 4 Bastionen ausgebaut wurde. 1638 wird sich auf dem Berliner Landtag über den schlechten Zustand der Festungswerke beklagt. Um die Stadt vor Angriffen von Norden besser zu schützen, wurde noch vor 1650 mit der Errichtung des Hornwerkes begonnen. Es entstand zunächst ein gedeckter Weg mit Graben gegen den Gohrin und gegenüber der Bastion Königin eine Schanze. Der Zustand der Festung wurde von Generalquartiermeister Holst 1650 dargestellt. Holst plante 1675 zudem die Verlegung der alten Oderbrücke an die alte Stelle vor dem Festungsbau mit einem Hornwerk und zwei Ravelinen
im Westen, sowie einen großen Brückenkopf mit drei Ravelinen auf dem Gelände der langen Vorstadt und des Kietzes.

Zur Ausführung gelangte dieser Entwurf des Brückenkopfes nicht. Bemerkenswert an diesem Planspiel ist die taktische Ähnlichkeit mit dem 1860 errichteten Lünettenring.
Ab 1643 wurden die Festungswerke aufwendig erweitert und instandgesetzt. Für die Aufbringung von Material, Arbeitskräfte und Verpflegung hatten die Stände und Städte des Kreises Sternberg zu sorgen. Eine Bezahlung der Arbeiten ist nicht nachgewiesen. Der Mühlgraben an der Bastion Königin war in den Jahren völlig versumpft und wurde nach 1650 zugeschüttet. In den Folgejahren wurde auch das Wehr an der Bastion Phillip erneuert und die versumpften Gräben der Festung gereinigt und gegen Versandung geschützt. 1662 wurden die Brustwehren nach holländischer Manier umgestaltet. Ab 1662 werden die Farcen der Bastionen geschlossen und überwölbt. Zwischen 1672 und 1677 entsteht die Bastion Brandenburg um den Flankenschutz der Oderbrück zu verbessern. Die Bastion wird massiv, ohne Kasematten ausgeführt. Unter der Herrschaft Friedrich III. entstand der gedeckte Weg "um die halbe Stadt".

Die Redane 2-12 wurden wahrscheinlich schon zum Ende der Regierungszeit Friedrich-Wilhelms etwa 1688 begonnen. Ende der 80er Jahren des 17.Jh. wurden das Hornwerk mit einer Kontereskarpe und einem Ravelin vollendet und der Ravelin "Christian Ludwig", auch "Schweinekopf" genannt, erbaut. Küstrin gilt nun als eine der stärksten Festungen Deutschlands und für den Stand der Waffentechnik des spätes 17.Jh. als uneinnehmbar.