Κατά την περίοδο της όψιμης αρχαιότητας (3ος -7ος) οι επιδρομές Γερμανικών αρχικά και Σλαβικών αργότερα φύλων οδήγησαν στην συρρίκνωση και τελικά στην εγκατάλειψη της Μίεζας. Οι κάτοικοι της περιοχής αναζήτησαν ασφαλέστερες θέσεις στο Βέρμιο, όπου θα τους βρούμε, όταν οι Οθωμανοί κατακτούν την Μακεδονία τον 15ο αι. Τότε περίπου ιδρύεται η σημερινή πόλη της Νάουσας. Στην προφορική παράδοση ως οικιστής φέρεται ο Οθωμανός μπέης των Γιανιτσών και κατακτητής της κεντρικής Βαλκανικής Γαζή Εβρενός. Εντυπωσιασμένος από την ομορφιά της περιοχής, ζήτησε από τον Σουλτάνο την άδεια να κτίσει μια καινούργια πόλη σε έκταση ίση με το τομάρι ενός βουβαλιού! Η άδεια δόθηκε και ο δαιμόνιος Τούρκος μπέης έλαβε το τομάρι του ζώου και το έκοψε σε λεπτή δερμάτινη λωρίδα. Περιέβαλε έναν χώρο βόρεια της Αράπιτσας με την λωρίδα, δένοντάς την σε τέσσερα παλούκια που έμπηξε στο έδαφος. Αυτά, σαν από θαύμα, έβγαλαν ρίζες και έτσι φύτρωσαν τα τέσσερα πλατάνια που σημείωναν τα όρια της παλιότερης Νάουσας. Από τα πλατάνια αυτά σώζεται σήμερα μόλις το ένα, ο Στραβός Πλάτανος κοντά στην Αγία Παρασκευή. Μέσα στα όρια που διέγραφαν οι τέσσερις πλάτανοι συνοικίστηκαν οι Χριστιανοί κάτοικοι των γύρω ορεινών οικισμών. Και η πόλη ονομάστηκε Νάουσα, αν και συχνά μαρτυρείται με το όνομα Νιά(γ)ουστα.
Η Νάουσα προικίστηκε από τους Οθωμανούς με ιδιαίτερα πολιτικά και οικονομικά προνόμια όπως η αυτοδιοίκηση, η μερική φορολογική ατέλεια, η προστασία της χάρη στην οικογένεια των Εβρενός και τον Σουλτάνο. Μ’ αυτά επιδιωκόταν η γρήγορη και απρόσκοπτη ανάπτυξη της περιοχής και η μεγιστοποίηση των προσόδων από αυτήν. Παρότι όμως η πόλη συνοικίστηκε με την πρωτοβουλία των Οθωμανών, φαίνεται εξαρχής πως είχε ελληνικό και χριστιανικό χαρακτήρα. Ο τρόπος της οριοθέτησής της μαρτυρείται ήδη από τα αρχαία χρόνια, ειδικά όμως στην Νάουσα, ο καθορισμός της θέσης των τεσσάρων πλατάνων έδειξε ότι οι δύο γραμμές που ενώνουν τα σημεία τους στον χώρο σχηματίζουν έναν νοητό σταυρό. Αυτό σημαίνει ότι από την ίδρυσή της κιόλας η Νάουσα ήταν μια σταυρωμένη, άρα καθαγιασμένη, προστατευμένη από τον Θεό, χριστιανική πόλη. Έτσι ίσως εξηγείται γιατί ήδη από την αρχή η παρουσία των Μουσουλμάνων στην πόλη ήταν ισχνή, κατέληξε δε κατά τον 17ο αι. να γίνει σχεδόν μηδενική.
