El 5 de septiembre de 1963 el Ramo de Guerra cede gratuitamente al Ayuntamiento los terrenos situados en «La Banqueta» colindantes con la Avda Héroes del Alcázar de Toledo (actual Avda del Ejército),para la construcción de un edificio destinado a este instituto, cuya creación se dispone en abril de 1964 por el Ministerio de Educación Nacional.
El Excmo Sr Ministro de Educación Nacional, por disposición de 5 de noviembre del citado año de 1964, consecuente a unánime acuerdo adoptado por el Pleno de esta Corporación Municipal en 28 de octubre anterior, autoriza la denominación de «Menéndez Tolosa» a este Instituto Nacional en consideración a la intervencion tan activa y eficaz del Excmo Sr D. Camilo Menéndez Tolosa, (General Gobernador Militar que fue de este Campo de Gibraltar, y por dicha fecha Ministro del Ejército) en pro de la enseñanza en general y de la creación de este Centro, que fue concluido en octubre de 1966, aunque inicia su actividad durante el anterior curso académico, utilizando la mitad de la edificación proyectada. Su capacidad máxima era de 1200 plazas para alumnos de ambos sexos y se halla dotado de modernas instalaciones pedagógicas y deportivas.
Fuentes: «Cien años de historia de La Línea» J.González de la Vega
En la actualidad se ha construido un segundo edificio cuyas obras finalizaron en el año 2007.
Se le conoce en La Línea como el “Instituto Viejo”.