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. turėjo 84, 1934 m. – 965, 1938 m. – 1545 eksponatus. Didžią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 laikytos 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 jo direktorė G. Christoforova, kovo mėn. – pirmasis mokslinis bendradarbis J. Alseika. Muziejus pavadintas Klaipėdos kraštotyros muziejumi. 1950 m. jis gavo tris kambarius 1855 m. statytame pastate Liepų g. 7, o po aštuonerių metų perėmė savo žinion visą pastatą. 1960–1962 m. atliktos rekonstrukcijos metu buvo pastatytas antrasis aukštas ir statinys įgavo dabartinį pavidalą. Ilgus metus čia dirbo muziejaus administracija, personalas bei fondai, – 2013 m. rudenį jie perkelti į naujas patalpas Didžiojoje Vandens gatvėje.
Pirmoji ekspozicija įrengta 1950 m. Tais metais 1542 eksponatus turėjusį muziejų aplankė 15 208 lankytojai. Kai 1966 m. Nidoje buvo įsteigtas muziejaus filialas – Kuršių nerijos istorijos muziejus, jam perduoti visi su Kuršių nerija ir mariomis susiję eksponatai. 1967 m. Kraštotyros muziejuje į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, o laikui bėgant – registruoti Klaipėdos rajono archeologinius paminklus, vykdyti žvalgomuosius archeologinius kasinėjimus, organizuoti mokslines ekspedicijas į Karaliaučiaus sritį. 1955 m. muziejus turėjo 2 791, o 1980 m. – jau 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 pastatus senamiestyje, Didžiojoje Vandens gatvėje. Čia per kelerius metus buvo įrengta nuolatinė ekspozicija, pristatanti Mažosios Lietuvos ir pirmiausia Klaipėdos krašto istorinę praeitį.
Laikui bėgant muziejus plėtėsi ir augo, atsirado atskiri jo padaliniai:
- 1992 m. prie Senojo turgaus, Šaltkalvių gatvėje, atidarytas Kalvystės muziejus.
- 2002 m. Klaipėdos piliavietėje, princo Frydricho poternoje pradėjo veikti Pilies muziejus, kuris iki pat šiol papildomas naujomis erdvėmis: 2006 m. – ekspozicijos tęsinys princo Karlo bastiono poternoje, 2018 m. – Muziejus 39/45, 2021 m. – archeologijos ekspozicija „Kurtina“.
- Nuo 2006 m. Mažosios Lietuvos istorijos muziejui pavesta rūpintis Klaipėdos Skulptūrų parko skulptūrų priežiūra, restauravimu, renginių organizavimu ir integravimu į miesto kultūrinę erdvę ir turizmą.
- 2014 m. Klaipėdos teritorinės muitinės pastate, buv. sovietinio valstybės saugumo (KGB) Klaipėdos padalinio rūsyje, įrengta Rezistencijos ir tremties ekspozicija.
Šiuo metu Mažosios Lietuvos istorijos muziejuje yra Archeologijos ir restauracijos, Etnografijos, Fondų apskaitos ir apsaugos, Istorijos, Edukacijos ir ryšių su visuomene skyriai.