Η ύπαρξη των Αρχείων Νομού Λέσβου, ξεκίνησε με την ίδρυση του Τοπικού Ιστορικού Αρχείου Μυτιλήνης στις 7 Σεπτεμβρίου 1987 (Π.Δ. 390/7-9-1987) που ήταν άμεσα εξαρτημένο από τα Γενικά Αρχεία του Κράτους σαν αποκεντρωμένη Υπηρεσία του.
Η ίδρυσή του ήταν βασισμένη στα αντίστοιχα άρθρα του Α.Ν.2027/ 1939 σχετικά με την αναδιοργάνωση της Υπηρεσίας των Γενικών Αρχείων του Κράτους και προϋπέθετε επίσης την εκφρασμένη θέληση των τοπικών φορέων, (κύρια του Δήμου Μυτιλήνης), ο οποίος σύμφωνα με τον Νόμο θα επιβαρύνονταν και με την λειτουργία του.
Στο Αρχείο σύμφωνα με την ιδρυτική πράξη, θα μεταβιβάζονταν όλα τα ιστορικά έγγραφα που φυλάσσονταν στην περιοχή Μυτιλήνης ή και αλλού καθώς και διάφορα αρχεία που θα παραχωρούνταν από Δημόσιες, Εκκλησιαστικές ή Δημοτικές και Κοινοτικές Αρχές ή από ιδιώτες, και θα είχαν σχέση με την ιστορία της περιοχής Μυτιλήνης.
Τα Αρχεία Ν. Λέσβου, μέχρι την επίσημη όμως ίδρυσή τους, σαν Μόνιμο Τοπικό Ιστορικό Αρχείο Μυτιλήνης, αντιμετώπισαν μια μικρή οδύσσεια καθυστερήσεων : από την έγγραφη αίτηση του Δημάρχου Μυτιλήνης Στρατή Πάλλη, στα 1984 (έγγρ. 5397/19-6-1984), μέχρι την γνωμοδότηση του Συμβουλίου Επικρατείας (προτάσεις Υπ. Προεδρίας, Υπ. Εσωτερικών, Υπ. Παιδείας και Υφυπ. Οικονομικών) για την επικύρωση της πράξης ίδρυσης στα 1986, πέρασε ένα χρονικό διάστημα τριών χρόνων.
Τελικά με το Π.Δ. 390/ 1987 ιδρύεται το Μόνιμο Τοπικό Ιστορικό Αρχείο Μυτιλήνης και με την παρουσία του Δημάρχου Μυτιλήνης, στις 19- 2- 1988, συγκροτείται και συνεδριάζει η πενταμελής Εποπτική Επιτροπή του, με θέματα:την εξεύρεση στέγης, την στελέχωση του Αρχείου και την συγκρότηση Eπιτροπής Eπιλογής των ιστορικών εγγράφων.
Η πρώτη εισαγωγή αρχειακού υλικού πραγματοποιείται στις 26- 9- 1988, με την παραλαβή προϊσχυσάντων βιβλίων Δημοτολογίου του Δήμου Μυτιλήνης, ακολουθεί στις 19- 10- 1988, η εισαγωγή αρχειακού υλικού του Πρωτοδικείου Μυτιλήνης, που θα αποφέρει το αρχείο του Εκκλησιαστικού Δικαστηρίου Μυτιλήνης και Mηθύμνης και την συλλογή των 45 Δικαστικών και συμβολαιογραφικών κατάστιχων στην παλαιά οθωμανική, ενώ στις 24- 11- 1988 παραλαμβάνονται και μεταφέρονται από το Ιστορικό Αρχείο Χίου, το αρχείο του Υπουργείου Διανομών και Επισιτισμού / Παράρτημα Λέσβου και 18 κατάστιχα στην παλαιά οθωμανική, οικονομικών υπηρεσιών του Ν. Λέσβου, που είχαν μεταφερθεί εκεί προς φύλαξη πολύ πριν την ίδρυση του Αρχείου.
Αρχές Δεκεμβρίου 1988 με εντολή του ΥΠ.Ε.Π.Θ. ολοκληρώνεται η στελέχωση της Υπηρεσίας με πρόσληψη προσωπικού με σχέση εργασίας μίσθωσης έργου και γίνεται η συντονισμένη έναρξη των εργασιών καταγραφής αρχειακού υλικού και εισαγωγής αρχείων. Άνοιξη του 1989 ξεκινάει ο πρώτος κύκλος εντοπισμού και καταγραφών αρχειακού υλικού σε όλη τη Λέσβο. Η ολοκλήρωση της επεξεργασίας της πρώτης αρχειακής εργασίας (Αρχείο Εκκλησιαστικού Δικαστηρίου Μυτιλήνης - Μηθύμνης) και των δραστηριοτήτων του Μ.Τ.I.Α. Μυτιλήνης, παρουσιάζονται στην πρώτη συνεδριακή συνάντηση των αρχειακών στην Κεφαλονιά το φθινόπωρο του 1989. Από το καλοκαίρι του 1989, αρχίζει η λειτουργία αναγνωστηρίου το οποίο με εξαίρεση την περίοδο της μετεγκατάστασης των Αρχείων και την εποχή της ετήσιας απεντόμωσης του αρχειακού υλικού, λειτουργεί αδιάλειπτα μέχρι σήμερα.
Με την υπ' αριθμ. Φ.5/ΙΣΤ/ 1030 υπουργική απόφαση του ΥΠ.Ε.Π.Θ. περί επιτροπών, από Νοέμβριο του 1990 η πενταμελής επιτροπή των Αρχείων αντικαθίσταται από επταμελή Εποπτική Επιτροπή που αντιπροσωπεύει όλους τους τοπικούς φορείς, και η οποία οριστικά θα καταργηθεί με την ψήφιση του Ν. 1946/ 91.
Από το 1990 δημιουργείται στη Λήμνο σταθμός συλλογής και διαμετακόμισης αρχειακού υλικού, με την παραχώρηση χώρου, κατ' αρχάς στο κτίριο του Παλλημνιακού Σχολικού Ταμείου και κατόπιν και μέχρι σήμερα σε κτίρια του Δήμου Μύρινας.
Τον Μάιο του 1991 ψηφίζεται ο Ν. 1946/ 91 "Γενικά Αρχεία του Κράτους (Γ.Α.Κ.) και άλλες διατάξεις" και σύμφωνα με το άρθρο 18 το Μόνιμο Τοπικό Ιστορικό Αρχείο Μυτιλήνης, μετονομάζεται σε Γ.Α.Κ.- Αρχεία Νομού Λέσβου, με έδρα την Μυτιλήνη.
To Σεπτέμβριο του 1991, τα Γ.Α.Κ.- Αρχεία Ν . Λέσβου συμμετέχουν στην ημερίδα που διοργάνωσε ο Δήμος Μυτιλήνης και το Πανεπιστήμιο Αιγαίου με θέμα "Γραπτές πηγές στην Λέσβο: Ο πλούτος των αρχειακών μας συλλογών", στην δε έκδοση των εργασιών της ημερίδας που ακολουθεί με τον ίδιο τίτλο, παρουσιάζεται σε επίμετρο επιλεκτικός κατάλογος των αρχειακών τους συλλογών.
Από Σεπτέμβριο του 1993 μέχρι και Ιούνιο του 1994 πραγματοποιείται η καταγραφή του Αρχείου Κοινότητας Πέτρας και διαμορφώνεται ο αντίστοιχος χρηστικός κατάλογος.
Το Νοέμβριο του 1994 το ΥΠΕΠΘ μισθώνει για τις ανάγκες των Γ.Α.Κ.- Αρχεία Ν. Λέσβου το νεοκλασικό κτίριο της οδού 8ης Νοεμβρίου 21- 23 στη Μυτιλήνη 480 τ.μ. και αρχίζει σταδιακά η μετεγκατάσταση της Υπηρεσίας.
Παράλληλα προωθείται η μηχανοργάνωσή της με δίκτυο Η/ Υ και αρχίζει η μεταγραφή των καταγραφών. Την ίδια εποχή φωτογραφίζονται οι τρεις πρώτοι κώδικες της Μητρόπολης Μυτιλήνης, με στόχο την μελλοντική ψηφιοποίησή τους.
Στις 26-7-1995 στο Πνευματικό Κέντρο Μανταμάδου "Ειρήνη και Φιλία" τα Γ.Α.Κ.- Αρχεία Νομού Λέσβου συνεργάζονται από κοινού για την διοργάνωση ημερίδας με θέμα: "Μνήμη και Ιστορία: Αρχείο Κοινότητας Μανταμάδου". Σαν επιστέγασμα δε των εργασιών καταγραφής του αρχείου την άνοιξη του 1991 και την άνοιξη - καλοκαίρι του 1994 πραγματοποιείται με έξοδα της Κοινότητας Μανδαμάδου η έκδοση αριθμημένου καταλόγου με τίτλο: "Αρχείο Κοινότητας Μανταμάδου 1783- 1991".
Το Νοέμβριο του 1996 τα Γ.Α.Κ. - Αρχεία Ν. Λέσβου για το σεμινάριο του Ε.Ι.Ε. του εκπαιδευτικού προγράμματος Leonardo da Vinci "Διαχείριση Βιομηχανικών Αρχείων" εκδίδουν επιλεκτικό κατάλογο Βιομηχανικών αρχείων Λέσβου.
Το καλοκαίρι του 1997 με πρόσκληση της Κοινότητας Μανταμάδου η ομάδα του Προγράμματος Εθελοντικής Eργασίας για το Περιβάλλον, με οδηγίες των Γ.Α.Κ.- Αρχεία Ν. Λέσβου επεξεργάζεται λυτά έγγραφα του αρχείου Κοινότητας Μανταμάδου. Στα πλαίσια της ενημέρωσης των εθελοντών εργασίας κατασκευάζεται ενημερωτικός- εκπαιδευτικός κατάλογος με τίτλο: "Αρχείο Κοινότητας Μανδαμάδου: ο ξανακερδισμένος χρόνος", ενω η επίσκεψη της ομάδας στα Γ.Α.Κ.- Αρχεία Ν . Λέσβου συνοδεύεται από την επετειακή έκδοση: "Χρονικό μιας πόλης και ενός Αρχείου: Γ.Α.Κ.- Αρχεία Ν. Λέσβου: Η πορεία τους μέσα στο χρόνο".
Τον Αύγουστο του 1997 , ομάδα ερευνητών του Ινστιτούτου Μεσογειακών Σπουδών, υπό την εποπτεία του καθηγητή Δημητριάδη, πραγματοποιεί καταγραφή των οθωμανικών εγγράφων και κατάστιχων που φυλάσσονται στο Αρχείο. Ακολουθεί η αποστολή καταλόγου.
Το καλοκαίρι του 1998, μετά από πρόσκληση του Δήμου Μυτιλήνης, η ομάδα του Προγράμματος Εθελοντικής Εργασίας για το Περιβάλλον, υπό την εποπτεία της Υπηρεσίας των Αρχείων Ν. Λέσβου και για διάστημα 15 ημερών πραγματοποιεί τις πρωταρχικές εργασίες επεξεργασίας και καταγραφής αρχειακού υλικού του Δήμου Μυτιλήνης που είχε παραδοθεί και φυλάσσονταν στα Γ.Α.Κ. - Αρχεία Ν. Λέσβου. Για την ενημέρωση των εθελοντών εργασίας κατασκευάζεται ενημερωτικός – εκπαιδευτικός κατάλογος.
Η ολοκλήρωση του κύκλου εργασιών κλείνει με την πραγματοποίηση έκθεσης αντιγράφων αρχειακού υλικού με θέμα: "Δημοτικό Θέατρο Μυτιλήνης: Μνήμη και Χρόνος Οράματα και Πραγματικότητες" που διαρκεί δύο εβδομάδες.

Αν και είχε προταθεί από τον Δήμο Μυτιλήνης αρχικά, μέρος του κτιρίου του Παλαιού Δημαρχείου στην Προκυμαία, για την στέγαση των Αρχείων, τελικά στις αρχές Σεπτεμβρίου 1988, αποφασίζεται από το Δήμο Μυτιλήνης, η ενοικίαση ενός ενιαίου χώρου 75 τ.μ. στο ισόγειο μιας νεόδμητης πολυκατοικίας στην οδό Ξενοφώντος 2 στην Μυτιλήνη. Το μίσθωμα του κτιρίου επιβαρύνει τον Δήμο Μυτιλήνης μέχρι και τον Νοέμβριο του 1994, χρόνο μετεγκατάστασης των Αρχείων στο σημερινό κτίριο των Γ.Α.Κ.- Αρχεία Ν. Λέσβου, αλλά η λειτουργία και τα έξοδα συγκρότησης της υποδομής του, παρέχονται εξαρχής από το Υπουργείο Παιδείας, φορέα στον οποίο υπάγονται μέχρι και σήμερα τα Αρχεία.

Τον Μάρτιο του 2001, πραγματοποιείται επέκταση των αρχειοστασίων του Αρχείου, με την ενοικίαση ακινήτων έκτασης ακόμη 235 τ.μ. συνολικά. Tο χειμώνα του ίδιου έτους ολοκληρώνεται στοιχειωδώς η διαμόρφωση και αρχίζει η λειτουργία εργαστηρίου συντήρησης.
Το Φθινόπωρο - Χειμώνα του 2001 με την παραχώρηση εκ μέρους του Δήμου Γέρας, του υπερώου του νεοκλασσικού κτιρίου του Δημαρχείου στα Γ.Α.Κ. - Αρχεία Ν. Λέσβου, δημιουργείται και η πρώτη αποκεντρωμένη αρχειακή μονάδα της περιφέρειας, που θα συγκεντρώσει εκτός άλλων, το αρχειακό υλικό της περιφέρειας Γέρας.