Początki dzisiejszej Gwardii sięgają 1946 roku i powołania przy Komendzie Powiatowej Policji w Koszalinie- Milicyjnego KS. Do ówczesnych założycieli klubu należał między innymi Stanisław Figas, którego imię nosi stadion przy ulicy Fałata 34. Początki nie były łatwe, o czym świadczy fakt, że krótko po powstaniu, decyzją administracyjną klub musiał zawiesić swoją działalność. Historia odrodziła się na nowo dwa lata później, wraz z powstaniem Zrzeszenia Sportowego Gwardia, przy którego pomocy reaktywowani Milicyjny KS. Nowo powstały w mieście klub przyjął nazwę Gwardia, by w swoim pierwszym meczu ulec w Szczecinku miejscowej Unii aż 0:8.
Pierwszym ważnym sukcesem Gwardii był awans do trzeciej ligi w 1954 roku. Inauguracyjna przygoda z tą klasą rozgrywkową nie była jednak udana o po roku gwardziści wrócili w szeregi ówczesnej „klasy A”.
Niezwykle blisko wywalczenia gry w drugiej lidze koszalinianie byli w sezonie 1962/63. Piłkarze Gwardii prowadzeni przez Leszka Wojciechowskiego w znakomitym stylu zwyciężyli w rozgrywkach okręgowych, lecz w decydujących bojach nie sprostali takim zespołom jak Zawisza Bydgoszcz czy Arka Gdynia i plany awansu do drugiej ligi zmuszeni byli odłożyć na kolejne lata.
Co nie udało się na początku lat sześćdziesiątych, udało się blisko dekadę później. Lata siedemdziesiąte przyniosły koszalińskiemu futbolowi wiele pięknych chwil. Głównymi autorami tych wspaniałych wydarzeń byli piłkarze Gwardii. Gwardia w tym okresie rozegrała sześć sezonów w drugiej lidze oraz odnosiła sukcesu w Pucharze Polski.
Inauguracyjny mecz na zapleczu ekstraklasy gwardziści rozegrali w sezonie 1973/74, a w premierowym meczu ulegli w Gdańsku Lechii 0:3. Spotkanie to obserwowało blisko 25 tysięcy widzów. Na pierwsze zwycięstwo nie czekano długo. Już w drugiej kolejce do naszego miasta przyjechała Lublinianka Lublin. Dla koszalińskich kibiców był to wspaniały mecz, bowiem zakończył się wygraną gospodarzy 3:1. Bramki dla drużyny prowadzonej przez Henryka Szczepańskiego zdobyli K.Michalak, Leszek Pałka oraz Zygmunt Michalak. W kolejnych siedmiu meczach beniaminek z Koszalina nie poniósł żadnej porażki, zostawiając w pokonanym polu takie zespoły jak Bałtyk Gdynia, Hutnik Kraków, Ursus Warszawa, Zawisza Bydgoszcz, czy wreszcie ogrywając w obecności ponad piętnastu tysięcy widzów po trafieniu Leszka Pałki- gdańskiego Stoczniowca.
Dwa lata później Gwardia odniosła największy sukces w 65- letniej historii klubu. Prowadzeni przez duet Jaremczak- Klemczak koszalinianie zaszli w rozgrywkach Pucharu Polski aż do ćwierćfinału, eliminując na swojej drodze takie firmy jak Pogoń Szczecin oraz Górnik Zabrze, którego wiodącymi postaciami byli wówczas tej klasy zawodnicy co reprezentanci Polski: Andrzej Szarmach, Jerzy Gorgoń, Zygfryd Szołtysik czy Henryk Wieczorek. Na drodze do półfinału stanął późniejszy triumfator- Śląsk Wrocław, z Władysławem Żmudą na czele. W tym samym sezonie zespół z Dolnego Śląska rywalizował również na arenie europejskiej w rozgrywkach Pucharu UEFA. Wojskowi w 1/8 finału zostali wyeliminowani przez sam Liverpool, którego barwy reprezentowali wówczas tacy gracze jak Kevin Keegan czy John Toshack.
Lata siedemdziesiąte to był znakomity okres w historii koszalińskiego klubu. To właśnie w tej dekadzie w Gwardii występowali tej klasy gracze co Marek Kaźmierczak, Leszek Pałka, Zygmunt Gilewski, Mirosław Okoński, Mariusz Niewiadomski, Stefan Mila czy Piotr Rzepka. Do juniorskich reprezentacji Polski powoływani byli także Krzysztof Mikulski oraz Jan Kosmalski. Na mecze do Koszalina na spotkania z naszym zespołem przyjeżdżały również kluby zagraniczne. Między innymi koreański Annokah Phenian czy Dinamo Tbilisi. W tym czasie Gwardia wpisała się na stałe w historii polskiej piłki, bowiem 18 tysięcy widzów na meczu w Poznaniu, pomiędzy Lechem a Gwardią w sezonie 1970/71, jest do dzisiaj rekordem frekwencji na spotkaniu trzeciej ligi.
W kolejnych dziesięcioleciach koszaliński zespół występował głównie w trzeciej i czwartej lidze, pojawiając się na zapleczu ekstraklasy w latach 80/81, 86/87 oraz 93/94.
Okres lat siedemdziesiątych to największe sukcesy piłkarzy. W kolejnych latach, ze zmiennym szczęściem i przerwami Gwardia Koszalin grała w II lidze. Ostatni sezon rozegrany w tej klasie rozgrywkowej przypadł na lata 1993/94. Następnie do sezonu 2003/04 Gwardia grała w III lidze. Później pogłębiające się kłopoty finansowe spowodowały, że klub znalazł się w głębokim kryzysie. Drużyna została wycofana z rozgrywek i w kolejnym sezonie rozpoczęła rywalizację w V lidze. W sezonie 2004/2005, na krótko doszło do fuzji z innymi koszalińskim klubem Granica, a rozgrywki na tym szczeblu Gwardia zakończyła awansem do IV ligi. W sezonie 2009/2010 piłkarze wywalczyli awans do III ligi a w sezonie 2017/2018 do II ligi.
Obecnie I zespół wystepuję w IV lidze.
