Około 1324-1326 miasto zostało ponownie włączone do Brandenburgii, a od 1373 leżało w granicach Korony Czeskiej. W 1402 zawarto porozumienie w sprawie sprzedaży miasta Polsce, jednakże ostatecznie czescy Luksemburgowie sprzedali je jeszcze w tym samym roku Krzyżakom. Po wybuchu wojny trzynastoletniej w 1454 Krzyżacy sprzedali miasto z regionem Marchii Brandenburskiej, aby pozyskać środki na prowadzenie wojny z Polską. mały|lewo|W latach 1535–1571 niemieckie margrabstwo Brandenburgii zostało podzielone na dwa niezależne państwa. Kostrzyn stał się stolicą wschodniego margrabstwa (Brandenburg-Küstrin). Jego jedynym władcą był Jan Hohenzollern, po którego śmierci Brandenburgia została ponownie zjednoczona. W latach 1535–1571 ze względu na dogodne położenie obronne margrabia Jan Hohenzollern przeniósł swoją rezydencję do Kostrzyna i rozpoczął przebudowę zamku oraz budowę potężnej twierdzy. Miasto stało się stolicą nowego margrabstwa – Brandenburgii-Kostrzyn, potocznie nazywanego też Nową Marchią. Jan Hohenzollern był protestantem. Kościół luterański był w Marchii kościołem państwowym. Brandenburgia-Kostrzyn dołączyła do ligi szmalkaldzkiej w 1538.