La loro origine è del tutto sconosciuta. Sembra attestato che gli Elimi non originassero da popolazioni greche (da qui la rivalità con la polis di Selinunte), ma fossero una mescolanza tra popolazioni autoctone, egee e forse liguri.
Elimo, nella mitologia greca, era un figlio illegittimo di Anchise. Al seguito d’Enea giunse in Sicilia. Ebbe diversi figli. Ma il racconto mitologico va oltre. Infatti narra che il principe Elimo, alla caduta di Troia, nel 1184 a.C, prese il mare con un gruppo di compagni verso la Sicilia, dove attraccò nella regione del Crimiso. Lo accompagnava l’amico Aceste. Dalla città distrutta partì anche il principe Enea con una ventina di navi e circa tremila troiani. Sbarcati a Trapani, i due gruppi finirono per ritrovarsi. La leggenda narra che, per onorare l’incontro, fondarono due città: dal nome Elima ed Egesta. Quest’ultima, successivamente, divenne Segesta, mentre Elima diede il nome alla regione, Elimica, e alla popolazione del luogo: gli Elimi.
Tuttavia, diverse fonti storiche, quali Ellanico e Dionisio di Alicarnasso, attestano la presenza di una popolazione autoctona, che conviveva con quella dei Sicani, “prima” dell’arrivo dall’Asia dei troiani. D’origine italica (forse genti scacciate dagli Enotri), o provenienti dalla Frigia, queste popolazioni si erano già insediate nella Sicilia occidentale già prima del sorgere della potenza militare di Micene. In questo periodo precedente si registrarono flussi di genti, provenienti dall’Epiro e dall'Illiria, verso il Veneto e la Liguria e da qui in direzione dell’Italia meridionale. E’ altrettanto probabile che non si formassero vere e proprie città, ma che vi fossero residenze diffuse sul territorio, con riferimenti a templi sacri, dedicati a divinità quali Afrodite dai Greci, Astarte dai Fenici, o Cibele dai Frigi, presso il monte di Erice.
I maggiori storici antichi attestano la derivazione troiana, o comunque Anatolica, degli Elimi. Ce lo confermano, infatti, sia  Tucidite che Plutarco.

Le principali città fondate dagli Elimi furono Erice (l’antica Erix), Segesta, Entella (nell’entroterra di Palermo) e Iaitias (nei pressi di San Giuseppe Iato).
La città più importante per gli Elimi fu senz’altro Segesta, che, infatti, fungeva a centro politico ed amministrativo del loro territorio. Fu in continua disputa con la polis greca di Selinunte e in genere con le popolazioni d’origine greca (sconfisse Selinunte nel 580 a.C.). Ciononostante, dagli scavi archeologici si attesta una forte influenza culturale ellenica a Segesta. Si sono rinvenuti un tempio dorico e un teatro d’origine greca alla sommità del Monte Barbaro. Coincidente con il porto di Castellammare del Golfo era situato l’emporium della città.
L’importanza di Erix era, invece, collegata alla religione. Il loro centro sacro, situato sul monte che domina l’odierna Trapani, faceva perno sul santuario di Afrodite, denominata Astarte dai Fenici e, successivamente, Venere dai Romani. Nel tempio si praticava la prostituzione sacra. L’emporium di Erix era posto sul mare a Drepanon (l’antica Trapani).