In origine, la città sorgeva su un isolotto che un breve tratto di mare separa dalla terra ferma, dove oggi si estende la parte nuova. Gli scrittori la descrivevano come un posto felice, con un clima mite, un mare pescoso ed un entroterra fertile, atto alla coltivazione  dell’ulivo e della vite; ciò che ci stupisce, è il mistero che ancora aleggia ancora nelle stradine, nelle strettoie, nei vicoli, attorno ai palazzi e  alle chiese (pittoresche pinacoteche), oltre alla magia sprigionata dalle sue mura di cinta teatro di numerosissime battaglie. Passeggiando per le anguste strade del centro storico di Gallipoli, si possono ancora trovare resti di civiltà vissute. 

La fondazione è attribuita da alcuni storici ad abitanti di un'omonima città siciliana, intorno al 390 a.c..; al dire di altri fu fondata dai messapi o dai cretesi. Alla sua nascita ed all'origine del suo nome sono, quindi, legate numerose leggende (anch'esse discordanti) tra cui quella di  Occo, figlio di Comer Gallo, da cui derivò l’antico nome “Gallopoli” ( ossia città che esce dal mare); quella di Lizio Idomeneo, che l’avrebbe fondata nel 1180 a.c. e quella dei Cretesi giunti nella penisola con Japige ,figlio di Dedalo che attribuì alla città  il nome di “Anxa” o “Anxur”.