Kostrzyn nad Odrą leży u ujścia Warty do Odry, w zachodniej części Kotliny Gorzowskiej (mezoregion), będącej największą częścią Pradoliny Toruńsko-Eberswaldzkiej (makroregion). Niewielka część Kostrzyna należy również do Kotliny Freienwaldzkiej, która rozpościera się głównie na lewym brzegu Odry na terytorium Niemiec. W Polsce należy do tej jednostki wąski pas doliny na prawym brzegu Odry od Kostrzyna do Starego Kostrzynka (gmina Cedynia). Północna część gminy zaliczana jest do Pojezierza Południowopomorskiego.
Pod względem historycznym Kostrzyn nad Odrą leży w dawnej ziemi lubuskiej, po opanowaniu go w 1261 przez Brandenburgię przejściowo stanowił także część Nowej Marchii.
Największą powierzchnię spośród form użytkowania terenu stanowią lasy i grunty leśne, które łącznie zajmują ponad 40% miasta. Jest to mniej niż średnia lesistość powiatu gorzowskiego, która wynosi 44,4%, ale znacznie więcej od średniej krajowej – 29,9%. Lasy znajdują się w północnej części miasta. Lasy te stanowią południową część Lasów Nadodrzańskich rozciągających się wzdłuż Odry od Kostrzyna do Gryfina. Ze względu na charakter, jaki posiada gmina – obszar jej stanowi tylko miasto Kostrzyn nad Odrą – stosunkowo niską powierzchnie zajmują użytki rolne (pastwiska, sady, grunty orne).