Bastion Magdeburg znajduje się pomiędzy Parsętą, ulicą Kamienną, Parkiem Jana Henryka Dąbrowskiego (i znajdującymi się tam pozostałościami Bastionu Pomorze z rowem fortecznym) oraz pasem bagien pomiędzy Kołobrzegiem a Budzistowem. To jedyny zachowany bastion fortyfikacji głównych Twierdzy Kołobrzeg, a jednocześnie jeden z najstarszych, powstały niedługo po wojnie 30-letniej.

W latach 1630-1631 trwało oblężenie szwedzkie Kołobrzegu. Miasto od 1627 roku okupowane było przez katolickie wojska cesarskie, które dopuszczały się wielu bezeceństw i były prawdziwym przekleństwem kołobrzeżan. Gdy 2 maja 1631 roku do Kołobrzegu wkraczali Szwedzi, nowy okupant był witany z radością. Jak twierdzono, ludzkości nic gorszego niż wojska cesarskie spotkać nie mogło. Szwedzi intensywnie fortyfikowali Kołobrzeg, tworząc na zewnątrz średniowiecznych murów miejskich wielobok bastionowy typu niderlandzkiego. Gdy 16 czerwca 1653 roku Kołobrzeg przejęła Brandenburgia, miastu nadano status twierdzy i kontynuowano budowę fortyfikacji.

Początkowo, w II połowie XVII wieku powstał półbastion (Kroczyński używa określenia "mały bastion" a Podruczny "Rawelin Magdeburg" - bastion zbudowany jest na planie pięcioboku, a rawelin na palnie trójkąta). Jego zadaniem była przede wszystkim ochrona stałego mostu na Parsęcie i funkcjonującego zapewne już w tym czasie Batardeau, ale także części Wyspy Solnej. Wówczas bastion nie miał jeszcze własnej fosy. Wraz z procesem inwestycyjnym, naprzeciwko półbastionu od strony ul. Basztowej powstał Bastion Cleve, a w Parku Dąbrowskiego Bastion Pomorze. Na początku XVIII wieku fortyfikacje Twierdzy Kołobrzeg były już gotowe i tak przetrwały do wojny siedmioletniej. Warto podkreślić, że były one obiektami ziemnymi, jedynie w dolnej części były murowane z kamienia polnego lub cegły. W samej twierdzy znajdowały się jedynie cztery prochownie, a tak żaden inny obiekt nie był odporny na bombardowanie artyleryjskie.Te niekonsekwencje polegające na niedoinwestowaniu twierdzy przed wybuchem wojny, zemściły się w jej trakcie.

Od 18 do 24 maja 1763 roku Kołobrzeg wizytował król Fryderyk Wielki. Obiecał odbudowę miasta ze zniszczeń wojny siedmioletniej i trzech oblężeń rosyjskich. Wkrótce wydał jednak polecenie przebudowy i rozbudowy twierdzy. Przygotowano projekt szacowany na 350 tysięcy talarów, ale prac nie rozpoczęto. Kolejne prace projektowe trwały w latach 1768-1770. Projekt przebudowy twierdzy wdrożono w życie, a prace prowadzono w latach 1770-1774. Wówczas przebudowano m.in. Bastion Pomorze i połączono go z Półbastionem Magdeburg, nadając mu formę bastionu. To tylko niewielka część prac prowadzonych w tych latach. Z tego okresu pochodzą zachowane fortyfikacje polowe twierdzy: Szaniec Ujście (później fort w porcie pasażerskim) oraz Reduta Bagienna w Porcie Jachtowym. W Kołobrzegu pracowały wówczas setki robotników, od 500 do ponad 2000 w zależności od okresu i źródeł, a także 100 lub więcej wozów. Niestety, nie mamy pełnych informacji o rozbudowie twierdzy, gdyż autor projektu spalił całą dokumentację po zakończeniu prac, które pochłonęły niemal pół miliona talarów. Do prac była również zmuszana okoliczna ludność.

Bastion Magdeburg był rozbudowywany w kolejnych etapach zmian w twierdzy, a po jej likwidacji w w 1872 roku przetrwał jako jedyny relikt fortyfikacji głównych. Ostatnie prace prowadzono na nim w 1853 roku. Pewne remonty wykonano także pod koniec lat 80-tych XX wieku. Dziś bastion jest parkingiem, ale mur jest w złym stanie technicznym, zwłaszcza od strony bagien. Rozsadzają go drzewa, a w niektórych miejscach doszło do zawału. Dlatego Towarzystwo Opieki nad Zabytkami zwróciło się do prezydenta Janusza Gromka z wnioskiem o rozpatrzenie możliwości wycinki drzew, odbudowy i zabezpieczenia muru, a wreszcie, wpisania obiektu do rejestru zabytków. Jest to zasadne z racji historii i wagi tego miejsca.

I na koniec ciekawostka. Na Bastionie Magdeburg znajdował się kamień z datą "1853", upamiętniającą ostatnią przebudowę obiektu. Niestety, ktoś go ukradł. Tymczasem kamień z taką samą datą, wyryty przy użyciu tej samej czcionki, znajduje się na łączniku pomiędzy bastionem a Parkiem Dąbrowskiego.