Im Laufe der Geschichte hatte die Stadt Bitola – abhängig von ihren jeweiligen Herrschern – viele verschiedene Namen.
Der slawische Name der Stadt, Bitola, stammt vom Wort Obitel, das im Mittelalter für eine Gemeinschaft von Mönchen, also ein Kloster, verwendet wurde. Die Stadt erhielt diesen Namen aufgrund der zahlreichen Klöster, die sich in der Stadt und ihrer Umgebung befanden, von denen einige bis heute existieren.
Mit der Zeit wurde der Laut O in der Aussprache des Wortes „Obitel“ weggelassen, und der Name der Stadt entwickelte sich zu Bitola.
Die Griechen nannten die Stadt aus demselben Grund Monastiri (Griechisch: Μοναστήρι).
Bitola ist heute der offizielle Name der Stadt, zugleich aber auch der älteste bekannte Name. Dies belegen die Bitola-Tafel aus dem Jahr 1015, auf der die Stadt erwähnt wird, ebenso wie Aufzeichnungen zahlreicher Militärführer von Zar Samuil sowie Berichte von Reisenden jener Zeit.
Der arabische Reisende Abu Abdallah Muhammad al-Idrisi schrieb im 12. Jahrhundert:
„Es dauert zwei Tage Reise nach Osten, um von Ahrid (Ohrid) nach Butili (Bitola) zu gelangen. Butili ist eine außergewöhnliche und schöne Stadt.“
Es gibt Überlieferungen, nach denen sich am rechten Ufer des Flusses Dragor 41 Kirchen befanden, mit derselben Anzahl an Wassermühlen zu ihrer Versorgung. Am linken Ufer des Dragor-Flusses soll es ebenfalls 29 Kirchen mit ebenso vielen Wassermühlen gegeben haben. An Feiertagen versammelten sich die Bewohner der Dörfer der Bitola-Ebene in diesen Kirchen, um ihre religiösen Riten zu vollziehen. Da das Gebiet, auf dem sich die Stadt Bitola damals befand, von zahlreichen Kirchen bedeckt war, erhielt die Stadt den Namen Manastir.
Einer anderen Version zufolge erhielt die Stadt den Namen Manastir nach einer großen Kirche, die sich oberhalb von Bitola befand, in der Nähe der heutigen Brücke, die Schwarze Brücke genannt wird (Türkisch: kara köprüsü). Diese Kirche soll groß genug gewesen sein, um alle Dorfbewohner aus der Bitola-Ebene aufzunehmen, die an Feiertagen zur Ausübung ihrer religiösen Riten kamen.
Nach den Aufzeichnungen von Marko Cepenkov wurde die Stadt Bitola nach dem Grundbesitzer Toljo benannt, der eine eigene Festung in der Nähe des heutigen Dorfes Bukovo bei Bitola besaß. Als die Türken kamen, um diesen Teil Macedonias zu erobern, riefen sie den Grundbesitzer Toljo zum Kampf mit den Worten „Bi Toljo, do bi Toljo“. Daraus, so Marko Cepenkov, soll der heutige Name der Stadt Bitola entstanden sein.
Während der osmanischen Herrschaft trug die Stadt den Namen Manastir, den die Türken und Albaner von den Griechen übernahmen. Nach den Balkankriegen von 1913 fiel die Stadt unter serbische Besatzung und erhielt wieder ihren alten Namen Bitola.