Intorno alle origini di Sternatia non esistono dati certi, ma soltanto delle ipotesi: si dice che sia stata fondata dai discendenti di Japige, o da soldati di Minosse di ritorno dalla Sicilia; secondo Tolomeo e Plinio, forse dal popolo dei Turnini o Sturnini che, per primi, avrebbero occupato la Magna Grecia.
Secondo lo scrittore G. Arditi, sarebbe sorta dall'unione di 7 villae ( masserie ).
Senza discutere su queste fonti, peraltro molto opinabili, certo è che le origini di Sternatia si perdono nel buio dei secoli.
E' probabile che l'origine di Sternatia risalga al IX – X sec. d. C., allorché ci fu nel Salento e, in particolare nella fascia interna, una costante immigrazione di clero secolare e regolare (monaci, "papades"), funzionari, mercanti, soldati, insomma di intere popolazioni provenienti dalla Grecia e dall'Oriente.
Il Salento, a causa delle continue guerre e relative devastazioni tra Bizantini, Longobardi ed Arabi, era rimasto pressoché deserto: lungo la fascia costiera si erano create vaste zone paludose, dove imperversava la malaria.
Con l'avvento al trono di Basilio I la nostra terra si ripopolò, grazie all'afflusso di genti, voluto dallo stesso monarca, provenienti dal mondo bizantino.
E' il caso di Galatina e Galatone, fondate da Galati provenienti dall'Asia Minore, o di Racale (da abitanti di Eraclea del Ponto).
Molti paesi della Grecìa (un tempo molto più vasta), tra cui probabilmente anche Sternatia, hanno questa origine: furono abitati inizialmente da famiglie di origine greca, che si dedicarono quasi esclusivamente all'agricoltura ed in particolare alla coltivazione della vite e dell'olivo.
Con l'avvento dei Normanni (XI sec.), re Tancredi elevò a feudo baronale Sternatia e ne fece dono al cavaliere Berlinghiero Chiaromonte. Da questo il feudo passò agli Orsini del Balzo, ai Cicala poi e finalmente ai Granafei che lo tennero fino alla fine del secolo scorso.
Nel 1481 il paese ospitò le truppe di Alfonso d'Aragona, al comando di Giulio Antonio Acquaviva, conte di Conversano, durante la spedizione per la liberazione di Otranto, già occupata dai Turchi.
