Na zachodnich obrzeżach miasta, nad wodami Odry, wznoszą się imponujące mury Twierdzy Kostrzyn. To „lektura obowiązkowa” dla odwiedzającego miasto turysty. Dzięki niej miasto od XVI w. kojarzone było z nowoczesną, imponującą i niezdobytą fortecą, wpływającą na losy całego regionu. Średniowieczne osady, powstałe u zbiegu dużych rzek, niemal zawsze miały strategiczne znaczenie militarne.
Twórcą zamysłu nowoczesnego umocnienia miasta był Jan Hohenzollern, który w 1535 r. otrzymał w spadku Kostrzyn wraz z Nową Marchią. Za jego panowania (w latach 1535–71) Kostrzyn stał się stolicą tej prowincji, co przyczyniło się znacząco do rozwoju miasta i wzrostu jego znaczenia oraz zadecydowało o budowie umocnień.
Twierdzy nadano kształt wydłużonego sześcioboku, początkowo z pięcioma pięciokątnymi bastionami, wzniesionymi na załamaniach obwałowania. Później, w 2. poł. XVII w., postawiono szósty bastion. W XVIII w. bastionom nadano nazwy: Król, Królowa, Książę, Księżniczka, Filip i Brandenburgia. Budowę podstawowych elementów umocnień zakończono pod koniec XVI w., po ok. czterdziestu latach intensywnych prac.
W czasie wojny trzydziestoletniej twierdza sprawdziła się jako schronienie – żadna z licznych, ciągnących przez Brandenburgię armii, nie zaryzykowała jej oblężenia. W okresie tej wojny rozpoczęto rozbudowę twierdzy, opatrując ją nowymi dziełami zewnętrznymi: rawelinami i szańcem przedmostowym. W 2. poł. XVII i na początku XVIII w. modernizowano ją jeszcze kilkakrotnie.
Warto wspomnieć, że utrzymanie skutecznej ochrony twierdzy odbywało się znacznym kosztem. Oprócz ciągłego dostosowywania obiektu do zmieniających się zadań garnizonu musiano także regularnie prowadzić bieżące remonty murów i wielokrotnie odmulać fosę. W latach 30. XVIII w. doszło do podmycia i zniszczenia bastionu Brandenburgia. Został on zrekonstruowany, jednak nadano mu mniejsze rozmiary.
Poza twierdzą rozwinęły się także przedmieścia Kostrzyna, nazwane od łączących ją ze stałym lądem szlaków – Krótkiej i Długiej Grobli. Krótkie Przedmieście było dzielnicą o charakterze rolniczym, zajmowało część terenu współczesnego miasta. Długie Przedmieście leżało na zachodnim brzegu Odry. Znajdowała się tam również rybacka chyża (drewniana zagroda), zamieszkiwana m.in. przez potomków słowiańskich rybaków, którzy – razem z ziemią lubuską – dostali się w połowie XIII w. pod panowanie margrabiów brandenburskich. Źródła historyczne podają, iż jeszcze na przełomie XVII i XVIII w. można było usłyszeć w tym miejscu język słowiański.
Twierdza została wystawiona na próbę w 1758 r., w czasie wojny siedmioletniej, kiedy to pod Kostrzyn dotarły wojska rosyjskie. Bombardowanie nie doprowadziło do zdobycia fortyfikacji, ale zniszczyło miasto. Na rozkaz Fryderyka II Wielkiego Kostrzyn odbudowano. Gdy w 1806 r. pod twierdzę podeszły wojska Napoleona, pamięć o katastrofie sprzed pół wieku sprawiła, że podjęto decyzję o oddaniu warowni Francuzom bez walki. Francuska okupacja trwała do 1814 r. W 1813 r. Prusacy odcięli twierdzę od otoczenia – po wielomiesięcznej blokadzie, wobec szerzących się wewnątrz głodu i chorób, zmuszona była kapitulować.
W 1872 r. Kostrzyn – obok Torunia, Poznania, Królewca i Spandau – znalazł się w grupie najważniejszych niemieckich twierdz wschodniej części cesarstwa przeznaczonych do rozbudowy. W cztery lata później powstał projekt przewidujący budowę wokół Kostrzyna ośmiu fortów. W 1886 r. ograniczono jednak ambitne przedsięwzięcie do niezbędnego minimum, wznosząc ostatecznie tylko cztery umocnienia. Usytuowano je tak, by zajmowały dominujące punkty w otoczeniu zbiegu rzek i węzła komunikacyjnego, pozwalając przy tym na kontrolę wychodzących z Kostrzyna szos i linii kolejowych.
Wraz z błyskawicznym rozwojem techniki wojennej, znaczenie militarne twierdzy szybko malało. Jeszcze przed I wojną światową zapadła decyzja o rozbiórce jej najstarszych, zupełnie już przestarzałych dzieł. Po wybuchu wojny wokół Kostrzyna rozbudowano nowy, obszerniejszy pas umocnień, opatrując go licznymi schronami i składami amunicji (wraz z nowymi koszarami w dwóch fortach było to łącznie 28 obiektów), w części zachowanymi po dziś dzień. Po zakończeniu wojny przystąpiono do planowanej rozbiórki niektórych dawnych umocnień wokół Starego Miasta, a w związku z rozbrojeniem Niemiec wiele obiektów wojskowych przekazano na cele cywilne.
Operacyjne znaczenie węzła przepraw u zbiegu Warty i Odry było jednak klątwą, od której miasto nie mogło się uwolnić. W 1945 r. twierdzę ponownie przysposobiono do obrony. Walki trwały dwa miesiące. W ich rezultacie miasto zostało doszczętnie zniszczone, a jego historycznego serca już nie odbudowano. Przetrwały tylko ruiny: pozostałości ulic, domów, zamku i kościoła. Dziś stanowią one „poligon” dla wyobraźni, podsuwającej obrazy tętniącego niegdyś życiem i pełnego uroku Starego Kostrzyna.
Z zabytkowych budowli twierdzy zachowały się bastiony: Król, Filip i Brandenburgia, wraz z przyległymi do nich, XVI-wiecznymi kurtynami. Stanowią one cenny zespół starej architektury obronnej, dający częściowe wyobrażenie o dawnej potędze Twierdzy Kostrzyn. Po latach niszczenia i stagnacji w okresie powojennym, twierdza przeżywa dziś swoją „drugą młodość”. Utworzono w niej imponujące muzeum (w podziemiach bastionu Filip), obecnie trwają szeroko zakrojone prace badawcze i remontowe, adaptujące tworzące ją obiekty do celów turystycznych. Warto wspomnieć, że za projekt ochrony i renowacji tych unikalnych budowli Kostrzyn nad Odrą zdobył w 2008 r. pierwsze miejsce w konkursie „Polska Pięknieje – 7 Cudów Funduszy Unijnych”.
Zwiedzając samodzielnie twierdzę, warto także przespacerować się mostem nad fosą i przejść przez bramę Chyżańską, znajdującą się po przeciwnej stronie twierdzy względem bramy Berlińskiej, a także zejść do kazamatów bastionu Filip, w których mieszczą się imponujące ekspozycje muzealne (godziny i zasady zwiedzania są dostępne na internetowej stronie muzeum), po czym wejść na ów bastion, skąd roztacza się malowniczy widok na Odrę, i przespacerować się promenadą Kattego. Następnie można udać się na spacer po bastionie Brandenburgia i, kierując się ku bastionowi Król i pobliskiej bramie Berlińskiej, przystanąć przy ruinach zamku i kościoła.