Cattolica Eraclea fu fondata nel 1610 dal Principe di Siculiana, in seguito ad una licentia populandi ottenuta dal re di Spagna; al nuovo insediamento abitativo fu dato il nome di Cattolica, in onore di Filippo III, Sua Cattolicissima Maestà. Dopo l'Unità d'Italia fu aggiunto anche il nome "Eraclea", per ricordare l'antica colonia greca, situata a poca distanza dal centro.
Eraclea Minoa fu fondata dagli abitanti della vicina Selinunte, originariamente col solo nome di Minoa, probabilmente ricollegandosi alla leggenda che vuole il re cretese Minosse inseguire Dedalo fin qui per punirlo dell'aiuto offerto ad Arianna e Teseo.
Gli scavi archeologici vennero intrapresi in maniera sistematica a partire dal 1950 e portarono alla luce un teatro greco del V sec. A.C., l'Antiquarium, le necropoli ed alcune abitazioni greche e romane, oltre ad alcuni tratti della cinta muraria.