Klub powstał na bazie założonego w 1957 roku KS Unia.
Nazwy: (1959) ZKS [Zakładowy Klub Sportowy] Celuloza -> (1992) MKS [Miejski Klub Sportowy] Celuloza -> (1999) KKP [Kostrzyński Klub Piłkarski] Celuloza
Pierwszy nabór do sekcji piłki nożnej przeprowadzono w 1957 roku.Pierwszą piłkę zakupiono z dobrowolnych składek członkowskich i rozpoczęto treningi na boiskach przy torach kolejowych.Trenerem społecznym był wówczas Jan Leśniewski.Już w 1959 roku drużyna w składzie: Jan Tomasik, Walenty Matuszek, Zbigniew Krzemiński, Eugeniusz Łuczak, Janusz Jędrzejczak, Jan Górecki,Bogdan Józefiaj, Kazimierz Leśniewski, Jan Biedak, Jan Klarzyński, Stanisław Sławok awansowała do rozgrywek klasy B.Awans do kolejnej wyższej klasy nastąpił w 1962 roku, kierownikiem sekcji był w tym czasie Jerzy Trepczyk, a trenerem Leon Grześ.Na koniec 1963 roku sekcja posiadała trzy drużyny biorące udział w rozgrywkach mistrzowskich: I zespół seniorów (klasa A), II zespół seniorów (klasa C) oraz zespół juniorów.Awans CELULOZY do klasy okręgowej nastąpił w 1969 roku i był wielkim sukcesem oraz radością kibiców.Właśnie wówczas powstał Klub Kibica, którego prezesem został Gerard Haśnik.Z chwilą uzyskania awansu do ligi okręgowej pierwsza drużyna została wzmocniona zawodnikami z innych klubów.Byli to: Kazimierz Malinowski, Stanisław Prokopowicz, Jan Adamowicz, Jan Goc, Jan Kisły, Bolesław Kruk, Julian Kowalczyk, i Alfons Dolny.Nowym szkoleniowcem został Adam Kaczorowski.W sezonie 1972/1973 klub doskonali się w klasie okręgowej, by rok później awansować do klasy wojewódzkiej, a zespół wzmacniają Zenon Chmielewski, Stanisław Kowalczyk, Marian Wiśniewski, Stanisław Łuczkowski i inni.Przychodzi 1978 rok, rok w którym piłkarze CELULOZY odnoszą największy sukces w historii klubu uzyskali awans do klasy międzywojewódzkiej, zdobyli Puchar Polski na szczeblu okręgowym oraz Puchar Przyjaźni. W tym czasie zespół seniorów tworzyli: bramkarze - Józef Socha i Janusz Górski ; obrońcy -Jerzy Jankowski, Marek Krawczyński, Hieronim Waligóra , Stanisław Łuczkowski, Marek Błaszkowski, Jerzy Grzebielucha , Adam Bogdański ; pomocnicy - Stefan Mirosław, Stefan Stefanik, Andrzej Ligenza, Zygmunt Bratkowski, Marian Wiśniewski ; napastnicy - Roman Żmijak, Kazimierz Malinowski, Zenon Szopny, Jerzy Żygielewicz , Wiesław Trzebiński, Jerzy Ziajka, Stanisław Kowalczyk , Jan Przybyła a trenowali zespół - Wiesław Piec a następnie Bogdan Łopaciński.Zespół juniorów awansował do ligi międzywojewódzkiej.Klub CELULOZA posiadał wówczas 17 osobową kadrę piłkarzy, trenujących dwa razy dziennie.Budowano silną drużynę, która w 1982 roku uzyskała historyczny awans do II ligi.Duszą piłkarskiego kolektywu w tym okresie był kierownik sekcji i drużyny Aleksande Michaluk.Drużyna pod wodzą Romana Sługockiego grała w następującym składzie: Janusz Górski, Zenon Mikołajczyk, Marek Krawczyński, Andrzej Krawczyński, Andrzej Kogut, Jerzy Żygielewicz, Ryszrd Kodzis, Waldemar Kowalczyk, Bogdan Babiracki, Marian Wiśniewski, Roman Żmijak, Krzysztof Wierzbicki, Reneusz Wachol, Jan Piasecki, Jan Oszmian, Arkadiusz Tański.Do legendy przeszedł pojedynek w 1/16 Pucharu Polski z ówczesnym mistrzem Polski Lechem Poznań rozegrany we wrześniu 1983 roku i zakończony porażką CELULOZY dopiero po trzech rzutach karnych.W latach 1984-1997 zespół występował w III lidze.Obecnie w IV lidze lubuskiej.Za swoją działalność CELULOZA otrzymała Srebną Odznakę PZPN w 2002 roku.Pierwszym obiektem sportowym z prawdziwego zdarzenia był istniejący do dziś zbudowany w latach 1962-1964 stadion sportowy składający się z głównej płyty piłkarskiej z widownią na 4 tysiące miejsc.Finansowanie działalności klubu do 1994 roku spoczywało na barkach patronackiego zakładu tj.Kostrzyńskich Zakładów Papierniczych.Obecnie działalność Miejskigo Ośrodka Sportu i Rekreacji finansowana jest z budżetu miasta.