Στην περιοχή του κατηργημένου σήμερα οικισμού του Ελευθεροχωρίου στα βορειοανατολικά της Παραμυθιάς, όπου βρίσκεται ένα από τα λιγοστά περάσματα ανάμεσα στους απροσπέλαστους ορεινούς όγκους της ανατολικής Θεσπρωτίας (Διάβαση Ελευθεροχωρίου), τα πρώτα ίχνη κατοίκησης ανάγονται στην Παλαιολιθική εποχή. Στο πλαίσιο των εργασιών για την κατασκευή της Εγνατίας οδού αποκαλύφθηκαν σημαντικές υπαίθριες θέσεις της Παλαιολιθικής εποχής (100000-10000 πριν από το παρόν), οι οποίες απέδωσαν έναν εξαιρετικά μεγάλο αριθμό λίθινων τεχνέργων, με δεσπόζουσα πρώτη ύλη τον πυριτόλιθο, καθιστώντας την περιοχή του Ελευθεροχωρίου τη μεγαλύτερη μέχρι σήμερα διερευνημένη θέση παλαιολιθικής δραστηριότητας, όχι μόνο στον ελλαδικό χώρο, αλλά και σε ολόκληρη τη Βαλκανική. Κατά τη διάρκεια των ίδιων εργασιών αποκαλύφθηκαν τα κατάλοιπα ενός παλαιοχριστιανικού οικισμού και ενός κλιβάνου του 5ου-6ου αιώνα.

Ο Αλή Πασάς, στο πλαίσιο της προσπάθειάς του να θέσει υπό τον έλεγχό του τους Σουλιώτες, οι οποίοι στις αρχές του 19ου αιώνα είχαν συνάψει κοινό μέτωπο εναντίον του με τους Τουρκαλβανούς μπέηδες της περιοχής, ανέγειρε στην περιοχή ένα ισχυρό κάστρο. Ο ίδιος φρόντισε για την κατασκευή ενός τελωνείου και ενός λαζαρέτου για την αντιμετώπιση της πανώλης στα εδάφη του πασαλικίου των Ιωαννίνων, τα κατάλοιπα των οποίων είναι ορατά σήμερα σε χαμηλό πλάτωμα του όρους Χαντακωμένου, κάτω από τη μικρή εκκλησία του Προφήτη Ηλία, στα νότια του κάστρου.