Στους δωρικούς χρόνους της Κρήτης, δηλαδή από το 1100  π.Χ. η περιοχή είχε την ονομασία Όρειοι, δηλαδή Ορεινοί.

Στο τέλος της κλασικής περιόδου, δηλαδή περί το 350 π. Χ. είναι γνωστά τέσσερα μεγάλα κέντρα-πόλεις, ἡ Έλυρος, κοντά στο Ροδοβάνι, η Υρτακήνα στο σημερινό ύψωμα Καρφί, νότια του χωριού Τεμένια, η Τάρρα, στη θέση του σημερινού οικισμού Αγία Ρουμέλη, και η Λισσός, στα παράλια. Λίγο αργότερα, στα τέλη των ελληνιστικών χρόνων , αναπτύχτηκαν και τρία άλλα κέντρα, η Κάντανος , η Σούγια και η Ποικιλασός.  

Το 293/2 π.Χ. οι  τέσσερις μεγάλες πόλεις στα νότια της σημερινής επαρχίας : ἡ Έλυρος, η Λισός, η Υρτακήνα και η Τάρρα, ακλουθώντας το παράδειγμα των άλλων πόλεων της νήσου, συνασπίζονται σε μια ομοσπονδία, που είναι γνωστή με το όνομα «Ομοσπονδία των Ορείων». Πρόκειται για μια συμμαχία των παραπάνω τεσσάρων πόλεων της νότιας περιοχής της επαρχίας, που συνάπτεται για λόγους ασφάλειας από εξωτερικούς κινδύνους, αλλά και για την ανάπτυξη της τοπικής οικονομίας.

Το 1204 η  Κρήτη περιέρχεται στους Βενετούς. Η πρώτη ισχυρή παρουσία της επαρχίας στους εθνικούς αγώνες της Κρήτης σημειώνεται κατά τη μεγάλη επανάσταση των Χορτάτσηδων (1272-1278). Ύστερα από την καταστολή της επανάστασης των Χορτατσών στο Σέλινο και την Κίσσαμο εξακολούθησαν οι εχθροπραξίες. Ο ενετός τότε δούκας της Κρήτης Μαρίνος Γραδενίγος  αποφάσισε να οργανώσει στην επαρχία μόνιμο κέντρο στρατιωτικής επιτήρησης, με ισχυρή δύναμη. Έκτισαν μόνιμο παράλιο φρούριο στην τοποθεσία, που ασφαλώς θα ονομαζόταν Σέλινο, στη σημερινή Παλιόχωρα. Οργανώθηκε έτσι το φρούριο Σέλινο (Castel Selino), με καστελάνο και στρατιωτική δύναμη ικανή να συγκρατεί τους φιλοπόλεμους και πολυτάραχους κατοίκους της επαρχίας, η οποία τώρα, από το όνομα του φρουρίου έλαβε την ονομασία Σέλινο.