Aunque es posible que los primeros en navegar por el peñón fueran los fenicios, los antiguos griegos creían que el héroe mítico Hércules abrió el estrecho de un solo golpe para poder unir el mar mediterráneo con el océano Atlántico para así seguir en busca del ganado de Gerion, rey del pueblo indígena Tartessos en Andalucía, que según cuenta la leyendas helénicas, era un gigante deforme.