The Cathedral of Holy Wisdom in Polotsk was built by Prince Vseslav Briacheslavich (r.1044–1101) between 1044 (it is first mentioned in the Voskresenskaia Chronicle under the year 1056) and 1066. It stands at the confluence of the Polota and Western Dvina Rivers on the eastern side of the city and is probably the oldest church in Belarus.

The cathedral is, like the Saint Sophia Cathedral in Kiev and Saint Sophia Cathedral in Novgorod, named after the Holy Wisdom of God. After building his own cathedral, Vseslav, who was an izgoi prince, tried to seize the Kievan throne. Failing in that attempt, he raided the surrounding principalities; in 1067, he raided Novgorod the Great and looted the Cathedral of Holy Wisdom there, bringing a bell and other loot back to decorate his own Cathedral of Holy Wisdom. The cathedral is mentioned in The Tale of Igor's Campaign, where it says that Vseslav would make nocturnal trips to Kiev as a werewolf and would hear the bells of Holy Wisdom at Polotsk as they rang for matins.

The cathedral has been significantly rebuilt and heavily modified between the eleventh and eighteenth centuries. Indeed, only parts of the church date back to the time of Vseslav, although the names of the builders are inscribed in a stone at the base of the cathedral: David, Toma, Mikula, Kopes, Petr, and Vorish. The burial vaults of 16 Polotsk princes dating back to the eleventh century have been uncovered (indeed, Vseslav himself, said to have been a sorcerer as well as a werewolf, was buried in the cathedral he built). According to the Voskresenskaia Letopis (s.a. 1156), the cathedral originally had seven domes,[3] later reduced to five after it was rebuilt following the fire of 1447. During 1596–1654 and 1668–1839 church was a Greek-Catholic (Uniate) cathedral. It was rebuilt again in 1618–1620 by Greek-Catholic Archbishop St. Josaphat Kuntsevych (rr. 1618–1623) following a fire in 1607, and again after a fire destroyed the cathedral and the city in 1643. In 1705–1710, Peter the Great and Aleksandr Menshikov used the church as a powder magazine; the magazine exploded. Over the next almost three decades (1738–1765), the Uniate archbishop, Florian Hrebnicki, rebuilt the cathedral. The Vilnius' architect Johann Christoph Glaubitz was responsible for the current appearance, which is an example of the "Vilnius Baroque" style. Currently it is a baroque structure with towers and the domes have been removed (or at least not rebuilt). The cathedral housed a library and other important cultural artifacts, but the library was destroyed when King Stephen Báthory of Poland took the city during the Livonian War in the late 16th century. The town was also occupied by the French during the Napoleonic Invasion in 1812 (indeed, two battles were fought at Polotsk in August and October, the second seeing house-to-house fighting) and also during the Nazi Invasion in the 1940s during which a large number of inhabitants were slaughtered