El antiguo edificio de la Comandancia Militar de Marina de Algeciras, y según informe del Comandante Militar de la época, construido en terrenos de varias cotas parecía no estar sobre terreno firme existiendo varias filtraciones.
Se propuso su reparación así como una ampliación del mismo. Debido a la construcción de un hotel y considerando que el edificio de la Comandancia Militar se quedaría separado de la bahía, el Comandante de Marina sugirió la construcción de un edificio de nueva planta en la parcela de terreno que fue ofrecida por el Ministerio de Obras Públicas en 1946.
La nueva Comandancia quedaría alineada con los edificios de la Junta de Obras del Puerto y de la Aduana y cuya construcción pudiera ser similar a la Comandancia de Marina de Cádiz, así como la cesión de la antigua al Patronato de Casas de la Armada.
El 17 de noviembre de 1954 se aprobó el proyecto de la Dirección de Construcciones Navales Militares para la construcción de un edificio para la Comandancia de Marina de Algeciras.
Por Decreto de 8 de junio de 1956, acordado en Consejo de Ministros fueron aprobadas las obras relativas a la construcción de un edificio con destino a la Comandancia de Marina de Algeciras. El 3 de abril de 1957 se llevó a cabo el replanteo de las obras para la construcción de la nueva Comandancia Militar de Marina. Sería construida en los terrenos denominados “Chorruelo”, perteneciente la Junta de Obras del Puerto.
En 1963 finalizaron las obras entregándose a la Armada, siendo su primer Comandante Militar de Marina el Capitán de Navío D. Francisco Zea. En la actualidad ubicada en suelos de la A.P.B.A. (Autoridad Portuaria Bahía de Algeciras).
El edificio tiene una planta cuadrada de 29.40 m de lado con patio central cubierto con cristales a la altura del techo de la planta primera. Consta de tres plantas, el torreón para el semáforo y dos cuerpos sobre las terrazas en cada una de las fachadas laterales. La planta baja, se destina a oficinas, cuartel de la dotación y servicios generales. La planta primera a oficinas, sala de juntas y despachos (Sr. Comandante y 2º Comandante), y la planta segunda dedicada para alojamientos.
Con la entrada en vigor de la Instrucción 81/2004 del Almirante Jefe del Estado Mayor de la Armada, quedó integrada en el Mando de Acción Marítima de Cádiz, perteneciente a la Fuerza de Acción Marítima, con la denominación de Comandancia Naval de Algeciras.