At Gibraltar on the European side, and near Tangier on the African, they marked the western extremity of the Mediterreanean Sea. See NASA photo at web address 1.
The phrase is first attested -- with Doric-dialect sta=lai -- in Pindar, in the 470s (Olympian 3.44, web address 2; Isthmian 4.12, web address 3), and again in Herodotus (2.33.3, 4.8.2; web addresses 4 & 5), by which time they had become topographically fixed; see also Strabo 3.5.2-6.
Although the noun in the phrase is, as here, routinely sth=lai, that noun in common usage meant a (flat) slab rather than a (round) pillar. The rare alternative *(hra/kleoi ki/ones (see under alpha 1143, mu 534) actually expresses roundness more aptly.
For the mythological alternative to Herakles in this context, Briareos, see beta 537.