Από τον 4ο αι. μ.Χ. η περιοχή του Πάρνωνα, αλλά και ολόκληρη η Πελοπόννησος, αποτελούσε τμήμα της Βυζαντινής Αυτοκρατορίας. Η χριστιανική θρησκεία διαδόθηκε από τον 6ο αι. μ.Χ. και μετά, όπως μαρτυρεί επιτύμβια επιγραφή που βρέθηκε στη θέση Παλιόστολος, Β-ΒΑ του χωριού Στόλος, όπου και τα ερείπια οικισμού παλαιοχριστιανικών χρόνων.
Τον 8ο αι. εμφανίστηκαν στην περιοχή σλάβικες φυλές (Μηλιγγοί και Εζερίτες), που εγκαταστάθηκαν στις δυσπρόσιτες περιοχές του Πάρνωνα. Οι κατά περιόδους εξεγέρσεις τους (από τον 8ο έως το 10ο αι.) καταστάλθηκαν από το στρατό του Βυζαντίου και οι ίδιοι, σιγά-σιγά, εκχριστιανίστηκαν και εξελληνίστηκαν. Οι Μηλίγγοι άφησαν αρκετά τοπωνύμια στην περιοχή, όπως τα «Μελιγγίτικα καλύβια» κοντά στο Άστρος, και το «Μελιγού» κοντά στον Αγ. Ιωάννη.
Κατά το 13ο αι. (Α’ Φραγκοκρατία) η περιοχή πέρασε σταδιακά στα χέρια των Φράγκων και των Ενετών, οι οποίοι, για να διασφαλίσουν την κυριαρχία τους, έχτισαν το φρούριο στο Γεράκι και το καστρί της Ωριάς στο Ξεροκάμπι.
Οι Τσάκωνες, μη αναγνωρίζοντας τη φραγκική κυριαρχία, έκαναν συχνά επιθέσεις εναντίον τους. Η καθυπόταξη των Τσακώνων και της ορεινής περιοχής του Πάρνωνα έγινε μετά την παράδοση της Μονεμβασίας στους Φράγκους (1250).
Ύστερα από τη μάχη της Πελαγονίας (1259) και την ανάκτηση της Κωνσταντινούπολης από τον Μιχαήλ Παλαιολόγο, η περιοχή επανήλθε στηνκυριαρχία των Βυζαντινών (1262). Όμως, οι εχθροπραξίες και οι λεηλασίες δεν είχαν σταματήσει. Η Πελοπόννησος δεν ευημερούσε πλέον. Οι Βενετοί εξακολούθησαν να ενδιαφέρονται για την περιοχή και έτσι το 1400 περίπου κατέλαβαν το Άστρος. Μερικά χρόνια αργότερα η περιοχή πέρασε στα χέρια τωνΤούρκων, που εισέβαλλαν στην Πελοπόννησο το 1460.
