Pierwszą próbę założenia muzeum w Koszalinie podjęło niemieckie Towarzystwo Naukowe już w 1879 r. Próba nie powiodła się i zabytki, głównie archeologiczne, przekazano w 1908 r. do muzeum w Szczecinie. Ponowne starania poczyniono w 1910 r., kiedy powstało Towarzystwo Krajoznawcze i Ochrony Kraju, w statucie którego znalazły się zapisy o utworzeniu muzeum. Pierwszą wystawę towarzystwo zorganizowało w 1912 r. w ratuszu staromiejskim i tę datę uważa się za początek działalności muzeum w Koszalinie.

W 1914 r. przydzielono muzeum (Heimatmuseum) pomieszczenia w Domu Miejskim (obecnie Poliklinika przy ul. Szpitalnej 2). Jednak dopiero w pięć lat później urządzono tam stałą wystawę. W 1929 r. muzeum otrzymało budynek przy ul. Gdańskiej (dzisiaj Marszałka J. Piłsudskiego 53). Prezentowano wówczas wystawy ze zbiorów archeologicznych, przyrodniczych, etnograficznych i zabytki sztuki. Heimatmuseum istniało do marca 1945 roku.

Po II wojnie światowej w budynku przy ul. Piłsudskiego (15 czerwca 1947 r.) dokonano otwarcia polskiego muzeum, które przejęło część zbiorów po dawnym Heimatmuseum. Do 1949 r. koszalińska placówka muzealna podlegała zarządowi miejskiemu. Od 1950 do 1958 r., już upaństwowione muzeum, podporządkowano bezpośrednio Ministerstwu Kultury i Sztuki, a pośrednio Muzeum Pomorza Zachodniego w Szczecinie. W latach 1958-1964 opiekę nad muzeum sprawowało Prezydium Wojewódzkiej Rady Narodowej w Koszalinie. W 1965 r. muzeum w Koszalinie zostało przekształcone w Oddział Archeologiczny Muzeum Pomorza Środkowego z siedzibą dyrekcji w Słupsku. Od maja 1969 roku dyrekcja Muzeum Pomorza Środkowego znajdowała się w Koszalinie, a muzeum w Słupsku stało się oddziałem.

Rok 1972 przyniósł kolejne zmiany w koszalińskim muzealnictwie. Powstała autonomiczna placówka pod nazwą Muzeum Archeologiczno-Historyczne w Koszalinie. Na cele wystawowe przekazano zabytkową kamieniczkę przy ul. Bogusława II 15. W następstwie zmian administracyjnych kraju 15 stycznia 1976 r. utworzono w Koszalinie Muzeum Okręgowe, które otrzymało w 1982 r. młyn i kamienicę młynarza przy ul. Młyńskiej 37-39. Jednocześnie zrezygnowało z sal wystaw czasowych znajdujących się w budynku przy ul. Bogusława II. Dwa lata później w odtworzonej na posesji przy ul. Młyńskiej chałupie rybackiej ze wsi Dąbki koło Darłowa umieszczono ekspozycję etnograficzną. W 1986 r. część działów została przeniesiona do nowej siedziby, a po upływie kolejnych pięciu lat otwarto pierwsze sale ekspozycyjne.

Od 1 stycznia 1999 r. placówka podlega Urzędowi Miejskiemu w Koszalinie a od 2000 roku nosi nazwę Muzeum w Koszalinie. Dziś muzeum posiada zbiory archeologiczne - głównie zabytki z terenu Pomorza, od neolitu po średniowiecze, historyczne - dokumentujące dzieje Koszalina i okolic od czasów najdawniejszych po współczesność, numizmaty, medale, zbiór ekslibrisów polskich i obcych, meble, wyroby rzemiosła artystycznego, sztuki - malarstwo dawne i współczesne, etnograficzne - zabytki rzemiosła, kultury i sztuki ludowej Pomorza.