Στην ακρόπολη των αρχαίων Φαρών και στην ευρύτερη περιοχή ως τα Ακοβίτικα, έχουν αποκαλυφθεί δείγματα ανθρώπινης παρουσίας τόσο κατά την Υστερορωμαϊκή όσο και κατά την Πρωτοβυζαντινή περίοδο – μια περίοδο κατά την οποία η σημασία της περιοχής ήταν μάλλον περιορισμένη.

Η γεωγραφική αυτή ζώνη χρησιμοποιήθηκε ως βάση και προπύργιο των Βυζαντινών, ιδιαίτερα μετά τον 7ο αι. Κατά τα φαινόμενα, μάλιστα, το κάστρο των Φαρών διαδραμάτισε σημαντικό ρόλο στην αντιμετώπιση των Σλάβων, που έφτασαν στην περιοχή στο δεύτερο μισό του 7ου αι., και απηχεί την επέκταση της βυζαντινής παρουσίας από τα παράλια προς τη μεσσηνιακή ενδοχώρα. Καθώς, μάλιστα, απέτυχαν να καταλάβουν την περιοχή των Φαρών, οι πληθυσμοί των Σλάβων εγκαταστάθηκαν αρχικά στην αρχαία κώμη «Καλάμαι», μετονομάζοντάς την σε Γιάννιτσα (σήμερα Ελαιοχώρι), στη Σέλιτσα (Βέργα) και στους ορεινούς όγκους του δυτικού Ταϋγέτου, για να εξουδετερωθούν οριστικά στα μέσα του 9ου αι.

Τα ιστορικά δεδομένα για την περίοδο μεταξύ του 6ου αι. (εποχή του Ιουστινιανού), κατά τον οποίο γίνεται η τελευταία αναφορά των Φαρών, στον Συνέκδημο του Ιεροκλή, και του 10ου αι., οπότε γίνεται η πρώτη μνεία της πόλης με το όνομα Καλαμάτα, είναι φτωχά. Στα δεδομένα αυτά συγκαταλέγονται έγγραφα που μαρτυρούν την πρώιμη ύπαρξη βασιλικής οδού και νομίσματα των 8ου και 9ου αι., σπάνιος φόλλις των αυτοκρατόρων Κωνσταντίνου ΣΤ΄ και Ειρήνης Αθηναίας (780-790 μ.Χ.) από τον Άγιο Φλώρο και φόλλις του Λέοντος ΣΤ΄ (886-912 μ.Χ.) από την Καλαμάτα.

Πρώτη γραπτή μαρτυρία της πόλης απαντά στο Βίο του οσίου Νίκωνος του «Μετανοείτε» (γράφτηκε το 1142 και ανατρέχει στην περίοδο 968-998), στον οποίο μνημονεύεται ως Καλομ(μ)άτα ή Καλαμ(μ)άτα. Η αναφορά αυτή επιβεβαιώνει τη στρατηγική θέση και τη σημασία ενός οικισμού που εντασσόταν στο θέμα της Πελοποννήσου, με έδρα την Κόρινθο, και ανήκε στη δικαιοδοσία της Μητρόπολης Πατρών. Ο οικισμός αυτός αποτελούσε ήδη πρωτεύουσα της Μεσσηνίας και απλωνόταν νότια και ανατολικά του κάστρου.

Κατά τα μέσα του 12ου αι., η Καλαμάτα είχε ήδη αποκτήσει μεγάλη σπουδαιότητα, διέθετε μονή που σχετιζόταν με τη Σπάρτη (πιθανότατα αυτή του κάστρου, που αναφέρεται στο Χρονικόν του Μορέως, το οποίο γράφτηκε κατά το 14ο αι. και περιγράφει γεγονότα του 13ου αι.) και αποτελούσε κόμβο του οδικού άξονα που συνέδεε την ορεινή με την παράλια νοτιοδυτική Πελοπόννησο. Στην ίδια περίοδο άλλωστε (11ος-12ος αι.) χρονολογούνται και οι αρχικές φάσεις σημαντικότατων θρησκευτικών μνημείων, όπως οι Άγιοι Απόστολοι, ο Άγιος Χαράλαμπος, ο Άγιος Κωνσταντίνος της μονής Καλογραιών και ο Άγιος Δημήτριος στη θέση Τούρλες.

ΤΟ ΟΝΟΜΑ
Στο τρίτο μέρος του Βίου του Oσίου Νίκωνος του «Μετανοείτε» (εκδόθηκε το 1142) η πόλη εμφανίζεται με το νέο της όνομα, Καλαμάτα. Εκεί παρέχονται τοπογραφικές πληροφορίες που ενισχύουν την προέλευση του ονόματος από τα καλάμια του Νέδοντα και της περιοχής, και πιο συγκεκριμένα από το λαϊκό τύπο «καλάματα». H άποψη αυτή ενισχύεται και από το γεγονός ότι υπάρχουν και άλλα τοπωνύμια που έχουν παραχθεί από το καλάμι (Καλάμι, Κάλαμος, Καλαμάκι). Άλλοι μελετητές υποστηρίζουν πως το όνομα προέρχεται από μια μονή αφιερωμένη στην Παναγία την Καλομάτα (η οποία, ωστόσο, δεν έχει ταυτοποιηθεί). Μια τρίτη εκδοχή θέλει το όνομα της πόλης να προέρχεται από κάποια γυναίκα με καλά μάτια ή με επίθετο Καλομάτα. Υπάρχουν, τέλος, απόψεις που θεωρούν ότι το όνομά της προέρχεται από το επίθετο Καλαμάτας, που σχηματίστηκε από το Καλομάτας.