Στη μακρά Βυζαντινή περίοδο η σχετική απομόνωση της επαρχίας καθώς και οι γενικότερες συνθήκες που επικρατούσαν, όπως και η ίδια η μορφολογία και η τραχύτητα του τοπίου, συνέβαλαν στην ίδρυση πολλών μοναστηριών στην επαρχία και στην προσέλκυση πολλών ασκητών. Αναφέρουμε τα μοναστήρια της Παναγίας Χρυσορροϊάτισσας και του Αγίου Νεοφύτου που εξακολουθούν και σήμερα να είναι σημαντικά, όπως και εκείνο της Μονής των Ιερέων (ή Αγίας Μονής). Πολλές από τις σωζόμενες στην επαρχία Πάφου εκκλησίες αποτελούσαν παλαιότερα ναούς μοναστηριών που άκμασαν κατά τα Βυζαντινά χρόνια ή και αργότερα. Εξ άλλου, μεταξύ των αγίων που ασκήτευσαν στην επαρχία της Πάφου σημαντικότεροι ήσαν ο Κύπριος άγιος Νεόφυτος* (ιδρυτής του αφιερωμένου σ' αυτόν μοναστηριού) τον 12ο-13ο αιώνα, και ο άγιος Ιλαρίων* ο Μέγας από την Παλαιστίνη τον 3ο αιώνα. Το ασκητήριο του δευτέρου προσπάθησε να βρει τον 5ο αιώνα ο πατριάρχης Κωνσταντινουπόλεως άγιος Γεννάδιος*, που πέθανε περιπλανώμενος στην επαρχία της Πάφου. Πολλοί άλλοι άγιοι και ασκητές έζησαν σε διάφορες εποχές σε διάφορα μέρη της επαρχίας Πάφου. Το πέρασμα όλων αυτών από την επαρχία συνέβαλε στην ανάπτυξη σ' αυτήν ενός έντονου θρησκευτικού συναισθήματος των κατοίκων της, που υφίσταται ως σήμερα. Η ύπαρξη τόσων πολλών εκκλησιών, ξωκλησιών, μοναστηριών και ασκητηρίων διαφόρων εποχών (περιλαμβανομένων αρκετών πρωτοχριστιανικών βασιλικών) που είναι κατάσπαρτα σ' ολόκληρη την επαρχία, είναι αδιάψευστη μαρτυρία της θρησκευτικότητάς της. Μιας θρησκευτικότητας που έπλασε ακόμη και ειδικούς αγίους προσαρμοσμένους στις τοπικές συνθήκες και ανάγκες, όπως για παράδειγμα οι άγιοι Αγαπητικός και Μισητικός ή ο άγιος Αμπέλης (= των αμπελιών). Η έννοια της αγάπης, που ξεκινά από την πανάρχαιη λατρεία της Αφροδίτης στην Πάφο, προσαρμοσμένη όμως στην Χριστιανική πίστη πλέον, θα πρέπει να σχετίζεται με την ύπαρξη του αγίου Αγαπητικού (Αρόδες, Πάφος) ή και τη λατρεία της Παναγίας ως Αγαπητιτζ'ής ή και ως Αφροδίτισσας ακόμη.
Οι παραλιακές κυρίως περιοχές της επαρχίας Πάφου υπέφεραν (όπως και όλα τα παραλιακά μέρη της Κύπρου) κατά την περίοδο των αραβικών επιδρομών (7ος-10ος αιώνας). Η ίδια η πόλη της Πάφου, που γνώρισε πιο πριν και ιδιαίτερα καταστροφικούς σεισμούς, υπέστη εκτεταμένες καταστροφές από τις επιδρομές αυτές. Εξ άλλου, για ένα σύντομο διάστημα, κατά τον 7ο αιώνα, στην Πάφο είχε εγκατασταθεί πολυάριθμη φρουρά Αράβων (προφανώς μαζί με τις οικογένειές τους) που όμως τελικά απεσύρθη. Έως τα Βυζαντινά χρόνια, και ξεκινώντας από τα Ρωμαϊκά και — ίσως — τα Ελληνιστικά, η Κύπρος ήταν διαιρεμένη σε τέσσερις επαρχίες εκ των οποίων εκείνη της Πάφου αναφέρεται ως Παφία και περιελάμβανε τη δυτική Κύπρο (οι άλλες τρεις επαρχίες ήσαν η Αμαθουσία, η Λαπηθία και η Σαλαμινία).
Οι Βυζαντινοί οικοδόμησαν κάστρα στην Πάφο και σε άλλα μέρη της επαρχίας, κατά την διάρκεια της μακράς διένεξής τους προς τους Άραβες, που τόσο αρνητικά είχε επηρεάσει ολόκληρη την Κύπρο με τις ιδιαίτερα καταστροφικές επιδρομές των Αράβων. Από την περιπέτεια του αγίου Νεοφύτου, γνωρίζουμε ότι στην Πάφο υπήρχε κάστρο στο οποίο ο άγιος είχε φυλακιστεί, όταν απ' εκεί δοκίμασε να φύγει με καράβι στο εξωτερικό. Σημαντικό οχυρό ήταν, επίσης, το κάστρο «Σαράντα Κολώνες», ερείπια του οποίου σώζονται στην Κάτω Πάφο. Κάστρο εθεωρείτο και ο «πύργος της Ρήγαινας» στον Ακάμα, όμως πρόσφατες έρευνες έδειξαν πως επρόκειτο μάλλον για μοναστήρι. Ωστόσο δεν ήταν ασυνήθιστη η οικοδόμηση μοναστηριών από τους Βυζαντινούς σε στρατηγικές τοποθεσίες, όπου τέτοια μοναστήρια εξυπηρετούσαν και κάποιες στρατιωτικές ανάγκες, λειτουργώντας κυρίως και ως παρατηρητήρια.
Η κατάληψη της Κύπρου από τους σταυροφόρους (1191) και στη συνέχεια η μεταβίβασή της στον οίκο των Λουζινιανών, τερμάτισε τη Βυζαντινή περίοδο της ιστορίας του νησιού που αποκόπηκε από τον κορμό της αυτοκρατορίας. Η οργάνωση της Κύπρου σε βασίλειο και ο κατατεμαχισμός της σε πολλά τιμάρια/φέουδα που εδόθησαν σε ξένους ευγενείς, ιππότες ή και τυχοδιώκτες ή και στη Λατινική Εκκλησία και στα ξένα θρησκευτικά τάγματα, επέφερε μια νέα τάξη πραγμάτων. Οι κάτοικοι της επαρχίας Πάφου, ακολουθώντας την κοινή μοίρα όλων των Κυπρίων, μετετράπησαν σε δούλους (πάροικους ή δουλοπάροικους) στην απόλυτη εξουσία και υπηρεσία των ξένων. Η πόλη της Πάφου απετέλεσε την έδρα διοίκησης της περιοχής. Τοπική έδρα διαμερίσματος (bailliage) αποτελούσε και η Πόλη Χρυσοχούς, που περιελάμβανε 12 χωριά.
Το χωριό Φοίνικας, εγκαταλειμμένο κι ερειπωμένο σήμερα, αποτελούσε την έδρα της Κομμανταρίας του Φοίνικος, μιας από τις κομμανταρίες του πανίσχυρου τάγματος των Ιωαννιτών ιπποτών στην Κύπρο. Έδρα μεγάλου φέουδου αποτελούσε και το χωριό Κούκλια (στον χώρο της αρχαίας Παλαιπάφου), στο οποίο σώζεται η (αναστηλωμένη) μεσαιωνική έπαυλη που ήλεγχε την παραγωγή της ζάχαρης στην περιοχή. Η ζάχαρη αποτελούσε βασικό προϊόν, ύστερα από την προώθησή της σε έκταση καλλιέργειας του ζαχαροκάλαμου. Στην τοποθεσία «Σταυρός» των Κουκλιών υφίστανται τα ερείπια εργοστασίου παραγωγής ζάχαρης.
Τα διάφορα χωριά της επαρχίας αποτελούσαν ιδιοκτησίες/φέουδα, άλλα της βασιλικής οικογένειας, άλλα της Λατινικής Εκκλησίας ή θρησκευτικών ταγμάτων και άλλα ευγενών και ιπποτών. Η ίδια η πόλη της Πάφου απετέλεσε όχι μόνο έδρα διοίκησης της περιοχής αλλά και έδρα Λατίνου επισκόπου. Η πόλη στολίστηκε με λαμπρά οικοδομήματα, όπως καθεδρικό ναό, ιδιωτικά αρχοντικά, φράγκικα λουτρά κλπ. Όμως κατά την περίοδο της Φραγκοκρατίας επλήγη σοβαρότατα από καταστροφικούς σεισμούς και γνώρισε παρακμή.
Κατά τη σύντομη περίοδο της βενετικής κατοχής της Κύπρου (1489-1570) η Πάφος εξακολουθούσε να μη αποτελεί σημαντική πόλη αλλά και η επαρχία της βρισκόταν σε σχετική παρακμή. Οι Βενετοί, που ενδιαφέρονταν σχεδόν αποκλειστικά για την άντληση όσο το δυνατό περισσοτέρων οικονομικών ωφελημάτων από την Κύπρο, με την εκμετάλλευση της κάθε είδους παραγωγής, δεν έκαμαν κανένα έργο υποδομής στην Πάφο ή την επαρχία. Αντίθετα, στις παραμονές της (αναμενόμενης) τουρκικής επίθεσης, χάλασαν το κάστρο της πόλης για να μη το βρουν οι Τούρκοι κατάλληλο για χρησιμοποίηση. Επικεντρώνοντας τις αμυντικές τους προσπάθειες αποκλειστικά στον άξονα Αμμοχώστου-Λευκωσίας-Κερύνειας, οι Βενετοί στην ουσία εγκατέλειψαν την πόλη της Πάφου και ολόκληρη την επαρχία. Αν και υπήρχαν ολιγάριθμες φρουρές σε διάφορα μέρη, ήσαν όμως εντελώς ανεπαρκείς στο να προβάλουν αντίσταση. Έτσι η πόλη της Πάφου, και ολόκληρη η επαρχία, κατελήφθη από τους Τούρκους το 1570 χωρίς προβλήματα για τους εισβολείς.