Δεν υπάρχει ασφαλής προσδιορισμός της ετυμολογίας του ονόματος της Βέροιας και υπάρχουν διάφορες εκδοχές περί αυτού. Σύμφωνα με γλωσσολόγους, η κατάληξη -ροια είναι παράγωγο του ρήματος ρέω και προσδίδεται σε πόλεις πλούσιες σε υδάτινα αποθέματα, πράγμα το οποίο ισχύει για την περιοχή της Βέροιας. Σύμφωνα με τη μυθολογία η Βέροια είναι κόρη του Ωκεανού και της Θέτιδος... ή κόρη του Αδώνιδος και της Αφροδίτης. Η πόλη λέγεται ότι κτίστηκε από το Μακεδόνα στρατηγό Φέρωνα, ο οποίος έδωσε στην πόλη το όνομά του (το γράμμα Φ εκείνη την εποχή στην περιοχή προφέρεται ως Β). Κατά την εκδοχή της μακεδονικής μυθολογίας η πόλη κτίστηκε από το βασιλιά Βέρητα, ο οποίος της έδωσε το όνομα της μιας από τις κόρες του. Τα ονόματα των γόνων του βασιλιά ήταν Βέροια, Μίεζα και Όλγανος και Ορέστης.
