The Bitola area is very rich in findigs from the prehistoric period. Two important ones are Velushka Tumba, and Tumba Bara near the village of Porodin.
During the ancient period the city became an important and relevant under the name Heraclea Lyncestis is an important settlement from the Hellenistic period till the Middle Ages. It was founded by Philip 2nd of Macedon in the middle of the 4th century BC. As an important strategic point it became a prosperous city. The Romans conquered this part of the ancient Macedonia kingdom in 148 BC and destroyed the political power of Heraclea. The prosperity continued mainly due to the Roman Via Egnatia road which passed near the city.
In the early Byzantine period (4th to 6th centuries AD) Heraclea was an important episcopal centre. Bitola was sacked by Ostrogothic forces, commanded by Theodoric the Great in 472 AD and, despite a large gift to him from the city's bishop, it was sacked again in 479 AD.
It was restored in the late 5th and early 6th century. In the late 6th century Bitola (then Heraclea) suffered successive attacks by Slavic tribes, who conquered Heraclea by the end of the century.
Bitola was conquered and remained part of the First Bulgarian Empire from late 8th. The spreading of Christianity was assisted by St. Clement of Ohrid and Naum in the 9th and early 10th century.
In the 10th century, Bitola was under the rule of Macedonian Tzar Samoil. He built a castle in the town, later used by his successor Gavrilo Radomir. John Skylitzes's 11th century chronicle mentions that Emperor Basil 2nd burned Gavrilo's castles in Bitola. In 1015, tsar Gavrilo Radomir was killed by his cousin Ivan Vladislav, who declared himself tsar and rebuilt the city fortress. To celebrate the occasion, a stone inscription written in the Cyrillic alphabet was set in the fortress where the Slavic name of the city is mentioned: Bitol.
Two important rebelions against Byzantine rule took place in the Bitola area in 1040 and 1072. In late 11th century, Bitola was incorporated within the Buglarian state lead by tzar Kaloyan. At the end of the 13th century Bitola was conquered again by Byzantium, but became part of Serbian kingdom after the conquests of Stefan Dusan, in the first half of the 14th century.
As a military, political and cultural center, Bitola played a very important role in the life of the medieval society in the region, prior to the Ottoman conquest in mid-14th century. On the eve of the Ottoman conquest, Bitola (Monastir on Turkish) experienced a great boom, having well-established trading links all over the Balkans.
From late 14th century to 1912, Bitola was part of the Ottoman Empire. Strong battles took place near the city during the arrival of Turkish forces. Turkish rule was completely established after the death of Prince Marko in 1395. For several centuries, Turks were a majority in this city, while the villages were populated mostly with Macedonians. Evliya Chelebi in his "Book of Travels" has noted that Bitola had 70 mosques, several coffee-tea rooms, a bazaar (market) with iron gates and 900 shops.
The city of consuls as Bitola is known even today, because 12 diplomatic consuls resided in Bitola during the period 1878-1913.
The wider Bitola region was a stronghold of the Ilinden Uprising. The uprising in the Bitola region was planned in Smilevo village in May 1903. Smilevo was defended by 600 rebels led by Dame Gruev & Georgi Sugarev, but when they were defeated, it was burned.
After the Balkan wars (1912-1913) and the division of the Ottoman province of Macedonia, Bitola got into the borders of Serbia, and during the First World war, it was almost burned down, since it was near the Macedonian Front (1916-1918). 25,000 inhabitants of Bitola have died and left.
During the Second World War, the Germans and later Bulgarians took control of Bitola. On November 4th 1944, the 7th Macedonian Liberation Brigade entered Bitola victoriously.