Olmutz is said to occupy the site of a Roman fort founded in the imperial period, the original name of which, Iuliomontium (Mount Julius), would have been gradually corrupted to the present form. Although this account is not documented except as oral history, archaeological excavations close to the city have revealed the remains of a Roman military camp dating from the time of the Marcoman Wars.

During the 6th century, Slavs migrated into the area. As early as the 7th century, a centre of political power developed in the present-day quarter of Povel (situated in lowland, southerly from the city centre). Around 810 the local Slavonic ruler was defeated by troops of Great Moravian rulers and the settlement in Olmutz-Povel was destroyed.

A new centre, where the Great Moravian governor resided, developed at the gord at Předhradí, a quarter of the inner city (the eastern, smaller part of the medieval centre). This settlement survived the defeat of the Great Moravia (c. 907) and later gradually became the capital of the province of Moravia. 

In 906 the first Jews settled in Olmutz. In 1060 they were forced into a ghetto and instructed to wear a yellow badge.

The bishopric of Olmutz was founded in 1063; centuries later in 1777, it was raised to the rank of an archbishopric. The bishopric was moved from the church of St. Peter (since destroyed) to the church of St Wenceslas in 1141 (the date is still disputed, other suggestions are 1131, 1134) under bishop Henry Zdík. The bishop's palace was built in the Romanesque architectural style. The bishopric acquired large tracts of land, especially in northern Moravia, and was one of the richest in the area.

Olmutz became one of the most important settlements in Moravia and a seat of the Přemyslid government and one of the appanage princes. In 1306 King Wenceslas III stopped here on his way to Poland. He was going to fight Wladislaus I the Elbow-high to claim his rights to the Polish crown, and was assassinated. With his death, the whole Přemyslid dynasty died out.

The city was officially founded in the mid-thirteenth century and became one of the most important trade and power centres in the region. In the Middle Ages, it was the biggest town in Moravia and competed with Brno for the position of the capital. Olmutz lost finally after the Swedes took the city for eight years (1642–1650).

In 1454 the city expelled the Jews of Olmutz, as part of a wave of anti-Semitism also seen in Spain and Portugal. The second half of the fifteenth century is considered the start of Olmutz's golden age. It hosted several royal meetings and Matthias Corvinus was elected here as King of Bohemia (in fact antiking) by the estates in 1469. In 1479 two kings of Bohemia (Vladislaus II and Matthias Corvinus) met here and concluded an agreement (Peace of Olmutz of 1479) for splitting the country.

Participating in the Protestant Reformation, Moravia became mostly Protestant. During the Thirty Years' War, in 1640 Olmutz was occupied by the Swedes for eight years. They left the city in ruins, and it became second to Brno.

In 1740 the town was captured and briefly held by the Prussians. Olmutz was fortified by Maria Theresa during the wars with Frederick the Great, who besieged the city unsuccessfully for seven weeks in 1758. In 1848 Olmutz was the scene of the emperor Ferdinand's abdication. Two years later, Austrian and German statesmen held a conference here called the Punctation of Olmütz. At the conference, they agreed to restore the German Confederation and Prussia accepted leadership by the Austrians.

In 1746 the first learned society in the lands under control of the Austrian Habsburgs, the Societas eruditorum incognitorum in terris Austriacis, was founded in Olmutz in order to spread Enlightenment ideas. Its monthly journal Monatliche Auszüge was the first scientific journal published in the Habsburg empire.

Largely because of its ecclesiastical links to Austria, Salzburg in particular, the city was influenced by German culture since the Middle Ages. Demographics before censuses can only be interpreted from other documents. The town's ecclesiastical constitution, the meetings of the Diet and the locally printed hymnal, were recorded in the Czech language in the mid-16th and 17th centuries. The first treatise on music in the Czech language was published in Olmutz in the mid-16th century. The political and social changes that followed the Thirty Years War increased the influence of courtly Habsburg and Austrian/German language culture. The "Germanification" of the town likely resulted from the cosmopolitan nature of the city; as the cultural, administrative and religious centre of the region, it drew officials, musicians and traders from all over Europe.

Despite these influences, the Czech language dominated, particularly in ecclesiastical publications throughout the seventeenth and eighteenth centuries. When the Austrian-born composer and musician Philip J. Rittler accepted a post at the Wenceslas Cathedral in the latter seventeenth century, he felt it necessary to learn Czech. With the continued dominance of the Hapsburgs and migration of ethnic Germans into the area, the use of Czech declined. By the 19th century, the number of ethnic Germans in the city were recorded as three times higher than the number of Czechs. After the 1848 Revolution in 1848, the government rescinded its Jewish expulsion order of 1454. Jews returned to the city and, in 1897, built a synagogue. The Jewish population reached 1,676 in 1900.

Olmutz retained its defensive city walls almost until the end of the 19th century. This suited the city council, because demolishing the walls would have allowed for expansion of the city and attracted more Czechs from neighbouring villages. The city council preferred Olmutz to be smaller and predominately German. Greater expansion came after World War II and the establishment of Czechoslovakia. Olmutz annexed two neighbouring towns and 11 surrounding villages, gaining new space for additional growth and development.

Serious tensions arose between ethnic Czechs and Germans during both world wars. During WWII, most of the town's ethnic German residents sided with the Nazis; the German-run town council renamed the main square after Adolf Hitler. World War II brought a rise in anti-semitism and attacks on the Jews that reflected what was happening in Germany. On Kristallnacht (10 November 1938), townspeople destroyed the synagogue. In March 1939, city police arrested 800 Jewish men, and had some deported to the Dachau concentration camp. During 1942–1943, ethnic Germans sent the remaining Jews to Theresienstadt and other German concentration camps in occupied Poland. Fewer than 300 of the town's Jews survived the Holocaust.

After Olmutz was liberated, Czech residents took back the original name of the town square. When the retreating German army passed through the city in the final weeks of the war, they shot at its 15th c. astronomical clock, leaving only a few pieces intact (these are held in the local museum). In the 1950s, the clock was reconstructed under the Soviet government; it features a procession of proletarians rather than saints. After the war, the Communist government participated in the expulsion of ethnic Germans from the country, as happened throughout eastern Europe, although many of these people had lived for two centuries in the region.

Despite its considerable charms, Olmutz has not been discovered by tourists in the same way that Prague, Český Krumlov and Karlovy Vary have. Its inner city is the second-largest historical monuments preserve in the country, after Prague.