La llegenda atribueix la seva fundació a Àstacos, fill de Posidó i de la nimfa Òlbia. Fou fundada com a colònia de Mègara, segons Mèmnon d'Heraclea en la 17a olimpíada (712-709 aC), i posteriorment fou annexada per Atenes, segons Estrabó. Per la seva banda, el Periple de Pseudo-Escílax l'anomena Òlbia (Ὀλβία), nom relacionat amb la mare d'Àstacos, l'heroi epònim, i no esmenta en cap moment el nom d'Àstacos.