Sovietinė valdžia ir ypač jos represinės įstaigos visada didelį dėmesį skyrė archyvams ir juose saugomiems dokumentams. Žinoma, ta „meilė“ dokumentams buvo pagrįsta ne domėjimusi istorija, bet galimybe ja manipuliuoti. Todėl visai nenuostabu, kad Antrojo pasaulinio karo metu sovietinės armijos kariams tik įžengus į „išvaduotos“ Lietuvos teritoriją, LTSR vidaus reikalų liaudies komisaras Juozas Bartašiūnas 1944 m. liepos 14 d. išleido įsakymą Nr. 1 skirtą archyvinių dokumentų surinkimui ir išsaugojimui. Įsakyme buvo nurodyta, kad „dokumentai turi didelę valstybinę reikšmę NKVD [vidaus reikalų liaudies komisariato] ir NKGB [valstybės saugumo liaudies komisariato] organų veiklai“. Visų NKVD apskričių ir valsčių viršininkams buvo įsakyta asmeniškai vadovauti apskričių archyvams ir teikti visokeriopą pagalbą renkant, tvarkant ir saugant sovietinių bei „vokiečių grobikų“ įstaigų ir organizacijų dokumentus.

Tikslių žinių kada pradėjo veikti archyvas Klaipėdoje nėra, tačiau žinoma, kad Klaipėdos miesto Vykdomojo komiteto 1945 m. birželio mėn. (diena dokumente nenurodyta) nutarimu Nr. 37 mieste veikusioms įstaigoms, įmonėms ir organizacijoms dviejų savaičių laikotarpyje jau buvo nurodyta sutvarkyti jų žinioje buvusius Lietuvos Respublikos ir vokiečių okupacinės valdžios įstaigų dokumentus ir perduoti juos Klaipėdos miesto valstybiniam archyvui.

Klaipėdos miesto valstybinis archyvas iš pradžių buvo Klaipėdos miesto Vykdomo komiteto Vidaus reikalų skyriaus žinioje ir pavaldus Lietuvos TSR vidaus reikalų liaudies komisariato (NKVD), vėliau – Lietuvos TSR vidaus reikalų ministerijos (MVD) Archyvų skyriui. Archyvui buvo skirtas mūrinio dviejų aukštų pastato pirmas aukštas tuometinėje J. Janonio gatvėje Nr. 10.

Jame tuo metu dirbo tik vienas darbuotojas – archyvo vedėjas. Patalpas sudarė keli kambariai, kurių bendras plotas buvo 58 m², dokumentų saugyklose buvo pastatyta 45 metrai lentynų. Archyvas aptarnavo ne tik Klaipėdos miestą, bet ir Klaipėdos apskritį (rajoną). Klaipėdos miesto valstybinis archyvas saugojo turimus, rinko po karo išlikusius dokumentus, juos tvarkė. Spėjama, kad pasitraukdami vokiečiai išvežė pagrindinę buvusio prieškarinio Klaipėdos archyvo dokumentų dalį, tačiau dalies fondų nespėta išvežti. 1947 metų duomenimis archyve buvo saugomos Klaipėdos apygardos teismo (1850 – 1900 metų), Klaipėdos policijos valdybos (1924 – 1939 metų), Klaipėdos krašto direktorijos (1930 – 1938 metų) ir kitų senųjų dokumentų fondų archyvinės bylos. 1948 metų duomenimis Klaipėdos miesto valstybiniame archyve buvo saugoma 20700 bylų ir 1,5 tonos dokumentų pabirų. Vėliau senieji ikikariniai dokumentų fondai buvo perduoti į Lietuvos TSR Centrinį valstybinį archyvą.

1956 metais Klaipėdos miesto valstybinis archyvas įkurdintas naujoje vietoje – septynių aukštų pastato septintame aukšte Žvejų g. 2.

1960 metais įsteigus Archyvų valdybą prie Lietuvos TSR Ministrų Tarybos, pasikeitė Klaipėdos miesto valstybinio archyvo pavaldumas. Tais pačiais metais archyvas buvo perkeltas į patalpas Priestočio g. 8.  

Metams bėgant archyvas pildėsi naujais Klaipėdos mieste ir apskrityje (rajone) veikusių įstaigų, įmonių ir organizacijų veikloje susidariusiais dokumentais. Nuo 1997 m. kovo 7 d. archyvas vadinosi Klaipėdos apskrities archyvu, o nuo 2017 m. sausio 1 d. prie archyvo prijungus Tauragės ir Telšių apskričių archyvus - Klaipėdos regioniniu valstybės archyvu. Šiuo metu jame saugomi 2167 archyviniai fondai, kuriuose yra daugiau nei 540 tūkstančių bylų, o dokumentų lentynos tęsiasi daugiau nei 7 kilometrus.

Klaipėda – ne tik seniausias Lietuvos miestas, tačiau ir vienintelis šalies uostas, Lietuvos langas į Europą, todėl Klaipėdos regioniniame valstybės archyve saugoma daugiausia su jūra susijusių įstaigų ir įmonių dokumentų.