Pirmieji bandymai įkurti Klaipėdoje muziejų datuojami XX a. pradžia. Kunigo dr. V.Gaigalaičio vadovaujamos draugijos „Sandora" 1906 m. pr. narių visuotiniame susirinkime buvo nutarta steigti biblioteką-muziejų. Draugijai įsigijus nuosavus namus, nuo 1912 m. ten pradėjo veikti biblioteka ir prie jos prisiglaudęs istorijos-etnografijos muziejus. Dėkodamas už padovanotus pirmuosius eksponatus, draugijos periodinis leidinys "Pagalba" prašė lietuvininkų „mums daugiau tokių senovės liekanų atgabenti. Jos namuose tikt išsimėto ir išprapuola, o„Sandoroje“ jos bus pakavojamos gražiai ir rūpestingai ateisiantiems čėsams“. Nėra duomenų apie šio muziejaus ekspoziciją ir eksponatų skaičių, nežinoma ir jo veikla po Pirmojo pasaulinio karo.

Klaipėdos muziejaus pradžia susijusi su 1924 metų įvykiais, kada krašto lietuvių ir vokiečių šviesuomenė įkūrė Klaipėdos krašto muziejaus draugiją „Memeler Landesmuseum e.V.“ 1924 m. birželio 20 d., kai įvyko šios draugijos visuotinis – kartais dar vadinamas steigiamuoju – susirinkimas, laikoma muziejaus gimimo diena (draugijos Įstatai buvo patvirtinti 1924 07 20, į draugijų registrą oficialiai įtraukta 1925 03 24). Draugijos pirmininku buvo išrinktas dr. V.Gaigalaitis, pavaduotoju – dr. Erich Scheu, raštvedžiu – gimnazijos mokytojas Fritz Ambrosius, jo pavaduotoju – dr. J. Žilius. Draugijos kasininku tapo J. Stikliorius, bibliotekininku – miesto bibliotekos vedėjas Dr. Kemp, o muziejaus valdytoju – archeologijos entuziastas majoras P. Tarasenka. Deja, po kelerių metų vokiečiai pasitraukė iš draugijos ir muziejaus tvarkymo veiklos. Muziejus neturėjo nuolatinių patalpų, negausūs buvo ir jo rinkiniai. 1931 m. muziejus turėjo 84, 1934 m. – 965, 1938 m. – 1545 eksponatus. Didžiąją jų dalį sudarė archeologiniai radiniai bei numizmatikos kolekcija. Iš archeologinių eksponatų gausiausias buvo apie 600 vnt. geležies amžiaus dirbinių rinkinys (ginklai, karoliai, sagės, apyrankės, antkaklės, žiedai, peiliai ir kt. iš Aukštkiemio, Lumpėnų, Vilkiškių bei kitų senkapių). Numizmatikos kolekcijos puošmena buvo II–III a. po Kr. Romos monetos. 

Paskutinis įrašas muziejaus dienyne datuotas 1939 m. kovo 12 d. Didžioji dalis prieškarinių rinkinių pražuvo, šiuo metu muziejaus fonduose saugoma vos keliasdešimt (daugiausia archeologinių) senojo muziejaus eksponatų. 

1948 m. Klaipėdos spaudoje pasirodė raginimų atkurti Klaipėdos muziejų. 1949 m. vasario 5 d. buvo paskirta pirmoji muziejaus direktorė G. Christoforova, kovo mėn. – pirmasis mokslinis bendradarbis J. Alseika. Muziejus buvo pavadintas Klaipėdos kraštotyros muziejumi. 1950 m. muziejus gavo tris kambarius sename (statytame 1855 m., rekonstruotame 1901 m.) pastate Liepų g. 7, o 1958 m. perėmė savo žinion visą pastatą. 1960–1962 m. atliktos rekonstrukcijos metu buvo pastatytas antrasis aukštas ir pastatas įgavo dabartinį pavidalą. Ilgus metus čia buvo įsikūrę muziejaus administracija, personalas bei fondai (2013 m. rudenį jie buvo perkelti į naujas patalpas Didžiojoje Vandens gatvėje). 

1950 m. buvo įrengta pirmoji ekspozicija. Tais metais 1542 eksponatus turėjusį muziejų aplankė 15 208 lankytojai. 1964 m. buvo įrengta pirmoji nuolatinė ekspozicija (1970–1971 m. ji buvo atnaujinta). Kai 1966 m. Nidoje buvo įsteigtas muziejaus filialas – Kuršių nerijos istorijos muziejus, jam buvo perduoti visi su Kuršių nerija ir mariomis susiję eksponatai. 1967 m. Kraštotyros muziejuje buvo įkurtas A. Každailio vadovaujamas Jūrų skyrius, ilgainiui išaugęs į savarankišką Lietuvos jūrų muziejų. 

Nuo 1954 m. muziejus pradėjo rengti išvykas eksponatams rinkti, 1959 m. pradėjo registruoti Klaipėdos rajono archeologinius paminklus, nuo 1960 m. vykdė žvalgomuosius archeologinius Klaipėdos apylinkių kasinėjimus. 1975 m. buvo surengta pirmoji muziejaus mokslinė ekspedicija į Karaliaučiaus sritį (1993 m. birželio mėn. – paskutinė). 1955 m. muziejus turėjo 2791, 1970 m. – 13 321, 1980 m. – apie 19 000 eksponatų. 

1988 m. birželio 17 d. Klaipėdos m. vykdomasis komitetas nutarė Klaipėdos kraštotyros muziejų pavadinti Mažosios Lietuvos istorijos muziejumi ir perduoti jam senovinius fachverkinius pastatus senamiestyje, Didžiojoje Vandens gatvėje. Ten per kelerius metus buvo įrengta nuolatinė ekspozicija, rodanti Mažosios Lietuvos ir pirmiausia Klaipėdos krašto istorinę praeitį. Šiuo metu lankytojai gali susipažinti su archeologijos, kartografijos, numizmatikos, etnografijos rinkiniais, Klaipėdos pilies ir miesto maketais, krašto ir miesto istorinę praeitį menančia originalia ir turtinga ikonografine bei dokumentine medžiaga. 

1992 m. rugpjūčio 5 d. prie Senojo turgaus, Šaltkalvių gatvėje, buvo atidarytas Mažosios Lietuvos istorijos muziejaus filialas – Kalvystės muziejus. Jame sukaupti nuo sunaikinimo išgelbėti Mažosios Lietuvos, senųjų Klaipėdos kapinių kryžiai, tvorelės, vartai, tik uostamiesčiui būdingos vėtrungės. Eksponuojami senųjų Klaipėdos kalvių autentiški darbo įrankiai, jų pagaminti namų apyvokos daiktai. 

Nuo 2002 m. Klaipėdos piliavietėje pradėjo veikti Pilies muziejus. Čia galima susipažinti su XIII–XX a. Klaipėdos miesto ir pilies raida: rodomi įvairių epochų miesto ir pilies maketai, piešiniai, planai, dokumentai, ginklai, fotografijos. 2018 m. Pilies muziejus pasipildė nauja ekspozicija MUZIEJUS 39/45. Joje interaktyviai, šiuolaikiškai, bet kartu ir jautriai pristatomas Klaipėdos miestui ir kraštui labai svarbus ir skaudus istorijos etapas – Antrasis pasaulinis karas.

Mažosios Lietuvos istorijos muziejuje yra Archeologijos-restauravimo, Etnografijos, Fondų apskaitos ir apsaugos, Istorijos, Edukacijos ir ryšių su visuomene skyriai.  

Nuo 2006 m. Mažosios Lietuvos istorijos muziejui pavesta rūpintis Klaipėdos Skulptūrų parko skulptūrų priežiūra, restauravimu, renginių parke organizavimu ir integravimu į miesto kultūrinę erdvę ir turizmą. 

2014 m. sausio mėn. Klaipėdos politinių kalinių ir tremtinių sąjungos, Mažosios Lietuvos istorijos muziejaus bei Klaipėdos teritorinės muitinės bendradarbiavimo dėka buvo atidaryta naujai parengta Rezistencijos ir tremties ekspozicija (S. Nėries g. 4, Klaipėda), buvusio sovietinio valstybės saugumo (KGB) Klaipėdos padalinio rūsyje (dabar Klaipėdos teritorinė muitinė).