Héraðsskjalasafn Vestmannaeyja var stofnað með formlegu samþykki menntamálaráðuneytisins 28. mars 1980, að fenginni umsögn þjóðskjalavarðar samkvæmt heimild í lögum nr. 7/1947 en þar segir: "að sýslunefnd og bæjarstjóra sé heimilt að koma á fót í sýslunni eða kaupstaðnum héraðsskjalasafni, er varðveiti á sem tryggilegastan hátt skjöl og aðrar ritaðar heimildir, sem snerta sérstaklega hlutaðeigandi sýslu- og bæjarfélag og ekki ber að afhenda Þjóðskjalasafninu."

Undirbúningur að stofnun safnsins var þó hafinn nokkru fyrr, eða árið 1978 þegar hafist var handa við að skrá í aðfangabók safnsins. Fyrir stofnun Héraðsskjalasafnsins voru skjöl varðveitt á Bókasafninu og Byggðasafninu. T.d. voru ljósrit af kirkjubókum Vestmannaeyja og fyrstu fundargerðabókum Bátaábyrgðarfélags Vestmannaeyja á Bókasafninu, en Byggðasafnið hafði í sýnum fórum merkilegt safn verslunarbóka frá 19. öld og fyrstu áratugum 20. aldar sem afhentar voru Byggðasafninu til varðveislu á 6. áratug þessarar aldar. Með því að skoða verslunarskjölin er hægt að rekja nokkuð heillega sögu verslunar í Vestmannaeyjum á seinni hluta 19. aldar og byrjun 20. aldar.

Héraðsskjalasafn Vestmannaeyja var 11 héraðsskjalasafnið sem var stofnað hér á landi. Fyrsti starfsmaður safnsins var Haraldur Guðnason fyrrum bæjarbókavörður í Vestmannaeyjum og starfaði hann við safnið allt til ársins 1989 að núverandi héraðsskjalavörður Jóna Björg Guðmundsdóttir tók við.

Safnið hefur frá upphafi verið staðsett í kjallara Safnahússins, en hefur þar að auki haft skrifstofuaðstöðu á miðhæð hússins.