Pirms Otrā pasaules kara pilsēta atradās Vācijā un tās vāciskais nosaukums bija Neištetina (vācu: Neustettin). 1310. gadā Pomerānijas grāfs Varcislavs IV piešķira Ščecinekai Lībekas tiesības. Pēc Trīsdesmitgadu kara Ščecineka iekļāvās Brandenburgā (vēlāk Vācijā). Otrā pasaules kara laikā Ščecineku 1945. gada 28. februārī ieņēma Sarkanā armija. Pēc kara pilsētas vācu iedzīvotāji tika padzīti, bet vietā ieradās poļi no PSRS ieņemtajiem Polijas apgabaliem.