Cuando la Guerra de Troya acaba, todo indica que Menesteo inicia un viaje pasando por diferentes poblaciones, gobernando unas y fundando otras, hasta que finalmente traspasa las Columnas de Hércules y llega a las costas del actual río Guadalete, donde atraído por el lugar funda una ciudad que será conocida con el nombre de Puerto de Menesteo.
La fundación de la ciudad parece tener un origen griego, pues recibe el nombre de Menesteo, pero los vestigios más antiguos hallados nos dan información sobre una ocupación fenicia a alrededor del siglo VI a. C. aproximadamente, encontrando necrópolis, murallas y viviendas.
Esto se debe a que la composición de ciudades fenicias siempre iban acompañadas de un puerto continental, es decir, Gadir, al igual que otras ciudades de origen fenicio como podría ser Tiro, está ubicada en una isla y por tanto rodeada de agua, a estas ciudades siempre se les procuraba un puerto en la costa, en este caso Puerto Menesteo.
Las diferentes hipótesis que podemos encontrar barajan múltiples posibilidades.
Las comunicaciones terrestres con la isla de León se han desarrollado, a lo largo de la historia, a través del puente Zuazo y sus predecesores.2 Sin embargo, existen también dos grandes puentes que unen la ciudad de Cádiz (asentada en la isla) con el resto del continente.