You have to give Barcelona credit for one of the more outlandish, self-serving state myths ever concocted. According to this, Hercules came to the highest point of Montjuïc after making the Pyrenees as a tomb for his lover Pirene. Even after stomping over those much higher mountains, he was impressed enough with the view of the plain below to vow he would one day return to found a great city.
During his later Twelve Labours, he was in command of a Greek fleet that ran into a raging mistral wind; eight ships found a safe anchor in Marseille, but the ninth went missing. After a search, Hercules discovered it safe and sound, tucked in at port under Montjuïc. Remembering his vow, he founded a city and named it the ‘ninth boat’, barca nona.
That's pretty cheesy, but Hercules, of course, has always been a good naturalized Spaniard. Who, after all, built the Pillars of Hercules down at Spain's southern tip? Ancient Greek and Roman mythographers identified their Hercules with dozens of similar gods and heros they encountered among the peoples of the Mediterranean. One of these was the Phoenician-Carthaginian Melkart. Temples to Melkart have been found in the Balearics and elsewhere around Spain. There was a famous one in Cádiz; Hannibal made a pilgrimage there before he marched on Rome.
Image by Yearofthedragon, GNU Free Documentation License