Proyectado por Juan Carlos Guerra en 1920, este edificio construido en piedra con un tamaño de 90 metros de largo por 11 de ancho.
El inicio de las obras data del año 1925 y no fue inaugurado hasta el año 1928 por los Reyes Alfonso XIII, María Cristina y Victoria Eugenia.
Originalmente, diversos elementos de la fachada sobresalían sobre la rasante del Paseo Nuevo. Estos elementos conferían al edificio matices regionalistas así como medievales, y fueron suprimidos para acentuar su carácter expresionista.
Las tres plantas originales fueron suficientes para albergar el Acuario, la Escuela de Pesca, las oficinas, la Sala de Juntas, el Museo y cinco laboratorios. Su planta inferior es confundida con el muro de costa de la Bahía de La Concha.
Ha sido ampliado en diversas ocasiones, debido a la complejidad de su disposición y escasez de espacio. En 1991, ampliado por Juan Manuel Encio y en 2008, reformado y ampliado por Hoz Arquitectos.
En 1998 tuvo lugar la inauguración de la ampliación del Palacio del Mar, a manos del arquitecto Juan Manuel Encio. Los trabajos fueron diseñados en 1991 y las obras iniciadas en 1995.
Las instalaciones originales se ampliaron añadiendo un edificio anexo bajo el Paseo Nuevo. El espacio resultante fue tres veces mayor que el original. Las instalaciones añadidas se extendían en espacios anexos al monte, y la zona de exposiciones se mantuvo en la parte de la edificación en fuerte contacto con el mar.
Se ampliaron las instalaciones del laboratorio, se incorporó un salón de actos y se creó el Oceanario, con un túnel bajo el agua, que proporciona una visión de 360º. Convirtiéndose así en una atracción de primera línea en la oferta cultural de la ciudad.
El proyecto de ampliación y reforma del edificio fue diseñado en 2001 por Ángel De La Hoz Escalera y Cristina Fontan Villanueva (Hoz y Fontan Arquitectos S.L.). El objetivo principal del trabajo fue reestructurar el edificio para depurar su estructura y mejorar la práctica museística.
El proyecto se ejecutó en diferentes fases, para permitir que el Aquarium permaneciese abierto durante todo el proceso de la reforma. En 2004 se crea un nuevo equipamiento hostelero, en la cubierta del edificio, directamente comunicado con el Palacio del Mar. En 2006 comienza la reforma del Palacio del Mar. El interior del Palacio del Mar es derribado para crear una nueva estructura interior. Los muros de sillares de la fachada se mantienen intactos.
Las nuevas instalaciones se abren en 2008, y la inauguración del complejo tiene lugar en 2009.
El conjunto resultante está formado por el rehabilitado Palacio del Mar, de tres plantas bajo el Paseo Nuevo, y un nuevo volumen sobre la rasante del paseo de dos plantas.
Los programas de servicio y gestión del edificio se establecen así en las zonas circundantes del conjunto del Palacio del Mar, ubicando el acceso y la tienda en el volumen externo apropiado por el Aquarium en el puerto. El restaurante se sitúa en la cubierta del edificio. Mirando al mar, su construcción recuerda a un barco varado en el puerto. A su vez, se mimetiza con el monte Urgull, y provoca así, una similitud con los fuertes del monte.
Los dos pisos superiores albergan el Museo Naval, y la planta baja expone diversas peceras. En el segundo de los sotos se sitúa la tienda.
Un itinerario continuo une todos los espacios museísticos en el interior. Por un lado, el Oceanario, un gran volumen de tres millones de litros de agua, en el que un túnel de metacrilato atraviesa el espacio para permitir una visión de 360º. Por otro lado, el segundo espacio expone diversas colecciones oceanográficas, en el que un esqueleto de ballena resalta por su gran tamaño de más de 14 metros. Finalmente el tercer espacio es dedicado a la historia marítima local.