El Archivo remonta su origen a la creación de los Departamentos Marítimos por Felipe V, en 1726. La ubicación más antigua que se conoce del mismo es la del almacén de San Campio, en el Arsenal Militar de Ferrol, si bien la documentación se hallaba distribuida en cuatro emplazamientos: Capitanía General (fondo militar), Jefatura del Arsenal (fondo industrial), Intendencia (fondo administrativo) y San Campio (fondo de generalidad), que hacía las veces de depósito central.
La saturación de estos locales obligó a tomar diversas medidas. Por una parte, se transfirió documentación al Archivo General del Ministerio de Marina y al Archivo General de la Marina "Álvaro de Bazán", en El Viso del Marqués (Ciudad Real). Y, por otra parte, se comenzó la búsqueda de nuevo inmueble. A este respecto, se dispuso el traslado del Archivo General del Departamento al Edificio de Servicios Generales de Capitanía, también llamado de Oficinas Militares, sito en la Calle María, de reciente construcción. El traslado de documentación, iniciado en 1958, no se terminó hasta 1970 y fue paralelo a las transferencias de documentación a Viso del Marqués. Las transferencias al Archivo General de la Marina tuvieron lugar entre 1954 y 1975. A partir de ese año y ante el colapso de este archivo histórico, se pasó a remitirlas al Archivo General de la Administración en Alcalá de Henares, en régimen de depósito. La última transferencia fue realizada en el año 1990. En total supusieron la salida de un total de unos 21.000 legajos, cuya datación más antigua se remontaba al año 1581.
En 1958 el Archivo pasó a ocupar el edificio de Servicios Generales de la Calle María, desde donde fueron trasladados sus
fondos documentales a los antiguos túneles de torpedos y misiles de la Estación Naval de A Graña y las dependencias de dirección, secretaría, oficinas y sala de consulta a la Sala de Armas del Arsenal de Ferrol en 2008. Estas últimas se trasladaron en 2012 a su actual ubicación en el Palacio de Capitanía General, junto con una pequeña parte de fondos, permaneciendo el resto de éstos en A Graña.
