L'Archivio di Stato di Messina, istituito come Archivio provinciale in esecuzione della legge organica sugli archivi del Regno del 1° agosto 1843 n. 8309, cominciò di fatto a funzionare il 31 luglio 1854. Divenne Archivio provinciale di Stato in forza del R.D. 22 settembre 1932 n. 1391; assunse poi la denominazione di Sezione di Archivio di Stato con la L. 22 dicembre 1939 n. 2006 e infine con il D.P.R. 30 settembre 1963 n. 1409 conseguì l'attuale denominazione.
Fin dalla prima metà del secolo XVII erano conservate in diverse stanze del palazzo del Senato di Messina, che sorgeva nella piazza del Duomo, "le pubbliche e le private scritture, strumenti e memorie antiche e moderne; gli archivi della corte stratigotiale e della città". L'Archivio municipale si conservava, invece, in una stanza al piano terra della torre del campanile del Duomo. Nel 1679, per ordine del Viceré Francesco Benavides, conte di Santisteban, l'archivio fu trasportato in Spagna perché in esso si conservavano i privilegi con cui erano state concesse a Messina le prerogative e le franchigie di cui aveva fino ad allora goduto e di cui ora veniva privata per la sua rivolta contro il governo spagnolo. Inoltre, a partire dal 1673, aveva cominciato a funzionare a Messina uno speciale archivio per la conservazione degli atti notarili: in tale anno, infatti, il Senato di Messina aveva adattato ad archivio due stanze del palazzo senatorio e rivolto istanza al Viceré, Claudio Lamoral, principe di Ligne, perché ordinasse che in esso fossero depositati gli atti dei notai defunti da coloro che ne erano in possesso. Il 20 aprile del 1673 il Viceré emanò un bando, dando quindici giorni di tempo per la consegna degli atti. Da questo archivio notarile, che fu uno dei primi del genere istituito in Italia, tra il 1895 e il 1896, furono versati 35.096 volumi notarili degli anni 1400-1840 all'Archivio provinciale di Stato, che già, dal 1854 in poi, aveva ricevuto gli archivi di uffici e magistrature soppressi e numerosi versamenti di documenti da parte di uffici e magistrature allora in funzione.
Dopo il terrificante terremoto del 1908 furono totalmente recuperati i fondi archivistici custoditi dall'Archivio provinciale. La loro distruzione si verificò, invece, il 25 maggio 1943, quando il deposito più grande dell'Archivio fu colpito da spezzoni incendiari durante una incursione aerea. Le fiamme che ne seguirono distrussero circa 100.000 pezzi, compromettendo in maniera grave e irrimediabile il patrimonio documentario ivi conservato, sicché, oggi, l'Archivio di Stato di Messina possiede molti fondi lacunosi e frammentari. Fra gli altri, andarono distrutti gli archivi del Consolato del Mare e dell'Intendenza borbonica e circa 35.000 volumi notarili.
