Il toponimo di Gagliano è di derivazione latina : secondo la tradizione, infatti, sembra che questa terra fosse appartenuta a un soldato romano di nome Gallo.
Lo stemma comunale rappresenta, invece, un gallo che si azzuffa con una biscia. 

E' probabile, tuttavia, che il primo agglomerato urbano sia sorto dopo la distruzione dei vicini casali di Plusano e Misciano (II secolo a. C.) e a mano a mano si sia sempre più esteso.

Dal 553 e fino all'XI secolo il paese entrò nella sfera di influenza bizantina, ma anche dopo l'avvento dei Normanni, il rito greco affiancò quello latino, fino agli inizi del 1600, quando morirono gli ultimi "Protopapi" greci di Gagliano.

Anche Gagliano del Capo, come tanti altri casali di Terra d'Otranto, è stata protagonista di varie vicende feudali.
Durante la dominazione angioina (secc. XIII-XV) divenne feudo di Isolda de Nocera, del milite francese Guglielmo Brunella, di Teodorico di Santo Blasio. Nel 1485 Gagliano fu, infine, concessa da Ferdinando di Aragona alla famiglia Castriota Scanderberg. Da questa casata nacque Giovanni che si distinse nella celebre battaglia combattuta il 7 ottobre del 1571 nelle acque di Lepanto e i discendenti abitarono nel castello di Gagliano.

Nel secolo XVII il feudo passò a Laura Guarini, principessa di Cassano e solo nel 1806 fu sciolto da ogni vincolo feudale.
Tuttavia ancora nel 1810 i gaglianesi dovevano sostenere una causa contro il barone di Alessano, il quale vantava alcuni diritti sul pesce pescato lungo il litorale.

Nel corso dei secoli questo paese ha subito i continui attacchi dei saraceni. Nel 1547 il pirata algerino Dragua sbarcava a Leuca e penetrava a Gagliano facendo ogni sorta di razzia; fu proprio i quella occasione che un monaco basiliano consigliò di fortificare il paese con le mura ("Via de lu Muru").
Solo dopo la battaglia di Lepanto, i Turchi limitarono le loro incursioni, eppure ancora nel 1624 attaccavano e depredavano il santuario di Leuca e poi sorprendevano alcuni contadini gaglianesi, intenti nel lavoro dei campi.