Tarih boyunca, hükümdarlara bağlı olarak, Bitola şehrinin birçok adı olmuştur.
Şehrin Slav adı olan Bitola, Orta Çağ boyunca bir keşiş topluluğu, yani bir manastır için kullanılan Obitel kelimesinden gelir. Adı, şehirde ve çevresinde bulunan ve bazıları bugün hala var olan birçok manastırın adını almıştır.
Zamanla, o sesi ‘Obitel’ kelimesinin telaffuzuna düştü ve şehrin adı Bitola oldu.
Yunanlılar aynı nedenlerle şehri Monastiri (Yunanca: μοναστήρι) olarak adlandırdılar.
Bitola bugünŞehir için resmi adı, ancak aynı zamanda en eski adı, 1015’ten itibaren şehrin adı geçen Bitola tabletine ve ayrıca Tsar Samuil’in birçok askeri komutanı ve o zamandan gelen gezginler tarafından değerlendiriliyor.
Arap gezgin Ebu Abdallah Muhammed el-İdrisi 12. yüzyılda şöyle yazmıştı:
‘Ahrid’den (Ohrid) Butili’ye (Bitola) ulaşmak için doğuya iki gün yolculuk gerekiyor. Butili alışılmadık ve güzel bir şehir.’
Dragor Nehri’nin sağ kıyısında 41 kilisenin ve onları desteklemek için aynı sayıda su değirmeninin bulunduğu hikayeler var. Dragor Nehri’nin sol kıyısında aynı sayıda su değirmeni bulunan 29 kilise de vardı. O dönemin tatillerinde, Bitola Ovası’nın köylerinden insanlar, dini ayinlerini yaptıkları bu kiliselerde toplandılar. Bitola şehrinin daha sonra bulunduğu arazi çok sayıda kiliseyle kaplı olduğundan, şehir Manastir olarak adlandırıldı.
Bitola şehrinin, Bitola’nın üzerinde, Kara Köprü (Türkçe: Kara Köprüsü) adlı mevcut köprünün yakınında bulunan büyük bir kiliseden sonra adını Manastir’e aldığını söyleyen bir versiyon var. Bu kilise, tatillerde dini ayinler yapmak için gelen Bitola Ovası’ndan tüm köylüleri ağırlayabilirdi.
Marko Cepenkov’un kayıtlarına göre, Bitola şehri, günümüzde Bitola’daki Bukovo köyünün yakınında kendi kalesine sahip olan toprak sahibi Toljo’nun adını almıştır. Makedonya’nın bu bölümünü fethetmeye, toprak sahibi Toljo’yu savaşmaya çağırmaya geldiklerinde, ona ‘Bi Toljo, Do Bi Toljo’ adını verdiler, bu da Marko Cepenkov’a göre Bitola şehrinin şu anki adının geldiği yer.
Osmanlı yönetimi sırasında, Türklerin ve Arnavutların Yunanlılardan benimsediği Manastir olarak adlandırıldı. 1913 Balkan Savaşları’ndan sonra, şehir Sırp işgali altına girdi ve eski adı Bitola’yı geri aldı.