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. Jóna Björg Guðmundsdóttir bókasafnsfræðingur tók við af Haraldi og gengdi stöðunni til ársins 2021. Hrefna Valdís Guðmundsdóttir, þjóðfræðingur, var ráðin héraðsskjalavörður við Héraðsskjalasafn Vestmannaeyja 1. janúar 2022.

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