Θρυλείται ότι ο Τουραχάν Βέης, που κατέκτησε τη Θεσσαλία το 1423, θεμελίωσε τον Τύρναβο όπου έκτισε τζαμί και ναό του Αγίου Νικολάου. Η μόνη πιθανή ιστορική αλήθεια που ο θρύλος ίσως απηχεί είναι ότι ο Τουραχάν υπήρξε «συνοικιστής» του Τυρνάβου, δηλαδή μετέφερε ανθρώπους από άλλες περιοχές και τους εγκατέστησε εκεί.
Ο ναός του Αγίου Νικολάου «του Ραχάν» όμως, που επισκευάστηκε το 1882 όπως μαρτυρεί εγχάρακτη επιγραφή, δεν είναι παλιότερος από τον 17ο αιώνα. Για να αποδείξει τη μεσαιωνική ύπαρξη του Τυρνάβου, ο συγγραφέας επικαλείται βυζαντινό κείμενο των μέσων του 10ου αιώνα που αφορά το «Μαρτύριο» του Αγίου Νικολάου του Νέου, ταξίαρχου στρατιωτικής λεγεώνας που ο Λέων ο Σοφός έστειλε στη Θεσσαλία για να αποκρούσει τους Άραβες. Επιπλέον, το όρος Τέρναβον που αναφέρεται στο κείμενο ταυτίζεται με το όρος Μελούνα (Κάτω Όλυμπος) που στις υπώρειές του βρίσκεται ο σημερινός Τύρναβος. Τέλος, οι εκσκαφείς των οικοδομών στην πόλη έφεραν στην επιφάνεια, καταστρέφοντας βέβαια την όποια διαστρωμάτωση, βυζαντινά όστρακα από πινάκια και σκύφους καθώς και τριποδίσκους κεραμικού κλιβάνου και λυχνάρια.
