La mitología clásica atribuye a Hércules, el héroe conocido por su fuerza y valor así como por sus muchas y legendarias hazañas (Hércules es el nombre romano del héroe griego Heracles), la gesta de haber creado el estrecho de Gibraltar apoyándose en dos columnas una en Calpe, antiguo nombre del peñón de Gibraltar, y la otra, en Abyla, la actual Ceuta. Homero, por su parte, hace referencia en La Odisea a Caribdis, el monte Hacho ceutí. La mitología nos explica que en su camino a la isla de Eritia para capturar los bueyes de Gerión, el monstruo de tres cabezas, Hércules erigió dos grandes columnas (los peñones de Gibraltar y de Ceuta, que bordean ahora el estrecho de Gibraltar, y que se representan en el escudo de la ciudad de Cádiz) como monumentos conmemorativos de su hazaña.

Aquellos primeros e intrépidos navegantes que se aventuraban al fin del munco conocido, eran perfectos sabedores que en sus estribaciones se encontrarían con las legendarias Calpe y Abyla, y que ésta última, la más meridional, tomaba la forma del Elephas, el elefante citado por el geógrafo e historiador griego Estrabón, para más tarde poder refugiarse en la bahía en la que más tarde se asentaría la ciudad de Ceuta. En el horizonte Átlas, aquel que luchó con los titanes en la guerra contra las deidades olímpicas y que tras su derrota y como castigo fue condenado a cargar eternamente en sus espaldas la tierra y el firmamento y en sus hombros la gran columna que los separaba.

Es a comienzos del primer milenio antes de Cristo cuando van a producirse los primeros contactos de los navegantes fenicios con la península ibérica y la zona de Ceuta, como una lógica etapa más de su expansión comercial por toda la cuenca del Mediterráneo. En principio estos contactos eran esporádicos pero pronto establecieron factorías en las costas atlánticas, entre las que destacarán Gadeira (Cádiz, con su legendaria fecha de fundación en 110 a. C.), en la ribera europea y Lixus (Larache), en la africana. La influencia fenicia no se limitará a un simple intercambio de objetos, sino que es un proceso que transformará las actividades económicas y la propia estructura social allá donde llegarán.

La expansión colonial griega llegará a las costas de la península dos siglos después de la fenicia. Es muy probable que los navegantes fenicios, helenos y púnicos contaran con algunas bases de apoyo en el litoral ceutí pero hasta el momento no se han encontrado gran cantidad de restos. Los únicos indicios hallados son unas cuantas monedas encontradas en el subsuelo de la Alameda de Colón, acuñadas en Gadeira y Malaka (Málaga); fragmentos de cerámica corintia de la segunda mitad del siglo II a.C. y una serie de ánforas, tanto grecoitálicas como púnicas, datadas en los siglos IV al II a.C.

La sistemática prospección que realizan los arqueólogos en el casco histórico de la urbe ha dado como resultado el hallazgo reciente de un poblamiento púnico en las inmediaciones de la actual Catedral ceutí, restos que se fechan en los siglos VII-VIII antes de Cristo.

Los fenicios establecerán Cartago como puesto comercial probablemente hacia finales del siglo IX a.C. Los primeros objetos desenterrados por los arqueólogos en el emplazamiento datan del 800 a.C. La ciudad es conocida por sus habitantes púnicos (nombre por el que los romanos identificarán a los cartagineses) o fenicios como la Ciudad Nueva, probablemente para distinguirla de Útica, la Ciudad Vieja.

Pero un peligroso rival entra en escena. Tras muchas guerras los romanos han conseguido dominar la península itálica y se dirigen hacia Sicilia, amenazando las colonias de Cartago. Se produce el inevitable choque entre las dos potencias de la época, son las llamadas Guerras Púnicas (de las que hubo tres), y que se desarrollarán hasta la victoria final de Roma. Tras la derrota de Cartago, el norte de África, la antigua zona de hegemonía de los fenicios, mantendrá durante un tiempo una cierta independencia. Ceuta pasará del Reino de Numidia al de Mauritania (ojo no confundir con la Mauritania actual, el antiguo reino mauritano se asentaba en el norte de África).

Desde la segunda mitad del siglo I a.C. se constata la presencia de un núcleo urbano en la zona que lleva desde el Foso navegable hasta el extremo occidental de la península de la Almina. Pomponio Mela se refiere a este núcleo como Septem Frates (los siete hermanos) en relación a sus siete colinas. La principal 'industria' de los lugareños es la elaboración de la salsamenta, especie de conserva hecha con el empleo de la sal y del famoso garum, un condimento nacido de la maderación de la caballa y que era muy popular en la época. La ciudad estaba integrada en el reino mauritano, cuyos soberanos eran aliados de Roma y participaban con uno u otro bando -según sus intereses- en las guerras civiles durante la República.

Con la llegada del Imperio a Roma, César Augusto se siente tentado, tras la muerte de su soberano, Boco, a incorporar al reino mauritano a sus territorios. Finalmente el emperador se decidirá por convertirla en una monarquía vasalla y pondrá al frente a Juba II, mauritano educado en Roma -una de las tácticas de Augusto era la de que sus aliados o estados vasallos mandaran a sus hijos para que fueran educados en la capital del Imperio-. Tras el asesinato de Ptolomeo, hijo de Juba II, se producirán una serie de revueltas entre las tropas mauritanas para enfrentarse a la 'dominación' romana -Ptolomeo era un rey títere-. Es entonces cuando Roma toma la determinación de conquistar el reino mauritano. Las tropas imperiales entran a sangre y fuego, destruyen mucha de sus ciudades y dividen el territorio de Mauritania en dos: Mauritania Cesariense y Mauritania Tingitana. La actual Ceuta, o la Septem Frates romana pertenecerá a la segunda.

Ceuta se convierte entonces en Civitas romanorum, o lo que es lo mismo, ciudad con estatuto jurídico de municipio romano. Este paso lo dará el Imperio para consolidar el poder de Roma sobre el 'Círculo del Estrecho', o lo que es lo mismo, el conjunto de ciudades de alto nivel económico que se encuentran en las costas del sur de la península y el norte de África -especialmente por su ocupación en la industria de salazón de pescado-.

La presencia de Roma en Ceuta es fácilmente constatable; las termas y el hallazgo de una sepultura romana (en la plaza de la Constitución) son solamente dos ejemplos de lo argumentado.