Le origini di Alezio così come le origini del suo toponimo sono incerte e discusse.
Si può dire solo con certezza che Plinio il Vecchio quando descrisse la Japigia, indicò la città di Alezio come una città fra le più importanti. Scrivendo anche che gli Aletini esistono grazie agli Japigi, che discendono dagli Osci, un'altra popolazione preromana, questa teoria è avvalorata dalle varie iscrizioni in testo messapico degli Osci trovate ad Alezio.
Nelle vicinanze di Alezio, in contrada Monte d'Elia, la Sovrintendenza Archeologica tra il 1981 e il 1985, ha portato alla luce una necropoli messapica extraurbana le cui origini risalgono tra il VI ed il IV secolo a.C. In questo sito sono stati trovati vari tipi di sepoltura: fosse nel terreno, cavi nella roccia, sarcofaghi.
Fino al II secolo a.C. non ci sono segni di abitazioni o di edifici di altro genere; non si hanno dati certi sulla estensione del centro abitato, le tombe sono state trovate sia all'interno che all'esterno dell'agglomerato urbano, secondo gli usi di sepoltura delle popolazioni indigene del Salento.
Con certezza risulta solo che Alezio nel VI secolo a.C. fosse un centro di rilievo per i continui scambi commerciali e culturali con la città di Taranto, spesso alleata, altre volte nemica. Alezio differiva dagli altri abitati messapici dell'epoca, come Oria, Cavallino, Ugento e Vaste per aver avuto un processo di urbanizzazione differente; ma non se ne conosce bene il motivo.
Infatti Alezio si trovava in una posizione di estremo privilegio, ubicata nel pieno della rete dei traffici commerciali della via Traiana, che permetteva la comunicazione ai centri più grossi dell'antica Messapia.
La vita di Alezio fu ininterrotta per tredici secoli, dal VII secolo a.C. al VI secolo d.C., durante tutto il periodo della epoca della Roma imperiale, e in questo lasso di tempo Alezio mantenne anche la sua influenza economica e culturale, grazie anche alla sua ubicazione rispetto alle vie di comunicazione, rispetto alle altre città salentine e rispetto a Roma.
Il nome di Alezio emerge nei documenti antichi in varie occasioni e sotto varie forme: di Aletia ne scrive Strabone; Aletium nei suddetti scritti di Plinio il Vecchio; Aletion in Tolomeo; Baletiun nella "Tavola di Peutinger" la più antica carta geografica del mondo.
In ogni occasione Alezio viene definita come centro popoloso e prosperoso, con fortuna ubicato nelle vicinanze del porto di Gallipoli e toccato dalle poche vie di comunicazione.
Nell'anno mille, Alezio venne distrutta di nuovo, questa volta dalle popolazioni Saracene; la popolazione aletina in questa occasione fuggì sulla isoletta di Gallipoli. E il vecchio abitato, o quello che ne rimaneva dopo l'incursione saracena, rimase abbandonato fino al XIII secolo, quando i monaci basiliani edificarono il tempio dedicato a Santa Maria della Alizza o Lizza. Questo fu l'inizio della ricostruzione dell'abitato sull'originario sito di Alezio, la rinascita però fu di un villaggio di dimensioni ridotte e così rimase fino al XVII secolo.
Si comincia a vedere una reale espansione e crescita demografica dell'abitato aletino all'inizio del 1700, quando il dottore in legge Gabriele Carlo Antonio Coppola proprietario di molte terre, concesse alcune di queste in enfiteusi perpetua a pochi contadini con l'intento di far costruire case che non fossero di campagna ma tipiche di un centro urbano, senza allevamenti di buoi, vacche, capre o altre bestie, con la sola eccezione di somari, cavalli e muli.
All'atto generoso del Coppola se ne accompagnarono altri, il prodigo Francesco Alemanno soprannominato "picciotto" e i latifondisti della famiglia Tafuri. Queste concessioni invertirono la tendenza, le attività agricole e commerciali ricevettero un forte stimolo, e così anche sotto il profilo demografico: gli abitanti da 200 divennero 2626 in poco più di un secolo.
Nel corso del 1700 e fino a oltre la metà del 1800 il paese venne denominato Villa Picciotti in onore dell'Alemanno. Il primo emblema di Alezio infatti raffigurava due bambini, i picciotti presi per mano. L'attuale stemma dell'araba fenice indica la forza della rinascita del paese.
Secondo un'altra ipotesi, meno accreditata, il nome di Villa Picciotti sarebbe dovuto alle presenza nel porto di Gallipoli di pescatori provenienti dalla Sicilia che dimoravano insieme alle famiglie in alcuni casolari intorno alla chiesa della Lizza. Nel 1854 Alezio ottenne l'autonomia amministrativa. Nel 1873, re Vittorio Emanuele II concesse la sostituzione del nome di Villa Picciotti in quello messapico di Alezio.