Gli studi e le ricerche effettuati negli ultimi anni, hanno rivelato come il Salento fosse abitato già nel Paleolitico medio. Nelle tante grotte dovute alla natura calcarea del territorio, sono stati rinvenuti utensili di selce. Probabilmente si trattava di ominidi appartenenti alla specie Uomo di Neanderthal, mentre quella dell'Homo sapiens sapiens si sarebbe diffusa nel Paleolitico superiore. Un'importante scoperta archeologica riguarda alcune statue ossee rinvenute nella Grotta delle Veneri presso Parabita, che dimostrano l'esistenza, già 20.000 anni fa, di culti riguardanti la fertilità. Un'altra testimonianza notevole della preistoria salentina è rappresentata da Delia, un'ominide di sesso femminile scoperto ad Ostuni. L'importanza di Delia è dettata dal fatto che essa conservava in grembo i resti di un feto in fase terminale, diventando quindi la più antica madre della storia di cui si conservino i resti. Questi resti rappresentano i primi consanguinei di cui si ha traccia del Paleolitico e dell’intera storia umana. La presenza di uomini nel Salento durante il Paleolitico e il Neolitico è documentata anche da interessanti graffiti, pitture, utensili, resti umani ed animali, anch'essi rinvenuti nelle grotte della penisola. Sicuramente notevoli per qualità e quantità sono le incisioni e i graffiti della Grotta Romanelli, presso Castro, e della Grotta dei Cervi, presso Porto Badisco. A Roca Vecchia hanno inoltre rinvenuto un imponente sistema di fortificazioni risalente all'età del bronzo (XV-XI secolo a.C.). Nella stessa area si trova un altro sito archeologico importante: la Grotta della Poesia, scoperta nel 1983; essa si sviluppa circolarmente su una superficie di 600 mq. e reca numerosissime iscrizioni votive, talvolta sovrapposte, di epoche e civiltà differenti, che risalgono al VIII-II secolo a.C. Altre importanti testimonianze ancestrali sono rappresentate da alcune costruzioni megalitiche nel territorio, come i dolmen, menhir e specchie, che nei secoli successivi furono adibite al culto del Cristianesimo.

I menhir (dal bretone men e hir "pietra lunga") sono dei megaliti (dal greco "grande pietra") monolitici (da non confondere con i dolmen, polilitici e solitamente assemblati a portale), eretti solitamente in età della pietra (neolitico, era preistorica), che potevano raggiungere anche più di venti metri di altezza, come ad esempio il Grand Menhir rotto di Locmariaquer (nel Morbihan in Bretagna). Menhir, insieme ai Dolmen ed alle Specchie (nati come fari neolitici utilizzate durante le battute di caccia e che si sono evolute in veri e propri sistemi di comunicazione), si trovano anche in Puglia, ed in particolare nel Salento. In provincia di Lecce, sono disseminati da per tutto. Ogni centro possiede almeno un menhir. Nel comune di Giurdignano, nei pressi di Otranto, se ne contano addirittura più di 15 esemplari. A Martano, in provincia di lecce, si ha la presenza del più alto menhir d'Italia, il "Menhir de Santu Totaru", che supera i 5 metri d'altezza. I menhir del Salento furono, nel medioevo, cristianizzati incidendo sulla pietra delle croci. Ancora oggi in alcuni paesi vi è l'usanza, la Domenica delle Palme, di fare delle processioni che terminano nelle vicinanze dei menhir dove vengono benedetti i ramoscelli di olivo.

Il dolmen è un tipo di tomba megalitica preistorica a camera singola e, insieme al sito di Stonehenge in Gran Bretagna, costituisce il più noto tra i monumenti megalitici. La realizzazione dei dolmen viene collocata nell'arco di tempo che va dalla fine del V millennio a.C. alla fine del III millennio a.C.. Particolarmente diffusi in Puglia nelle campagne salentine e nel barese, dove sono concentrati nel territorio di Bisceglie, nei pressi dei crocevia delle antiche vie di comunicazione con i paesi vicini (Trani, Ruvo di Puglia, Terlizzi e Molfetta) dove se ne contano quattro e, forse, addirittura cinque, mentre discorso a parte merita quello scoperto in tempi relativamente recenti (inizio degli anni novanta) nel territorio di Giovinazzo lungo la direttrice verso l'interno che porta a Terlizzi e Bitonto. Nel Salento i dolmen sono situati nei centri di Giurdignano, dove se ne contano sei, Minervino di Lecce, Cocumola, Giuggianello, Melendugno, Maglie, Corigliano d'Otranto, e Salve.