The Medieval Rus was a collection of petty states, united only by a feeble felling of unity coming from a common ancestor - the legendary jarl Rurik. Through the first two centuries of statehood this seemed enough to keep the Kievan Rus a coherent and stable political force. This, however, ended in 1054 with the death of prince Yaroslav the Wise. His will divided the state between his sons, effectively ending the period of unity and stability.
Things were different in Polotsk, however. Rulers of this domain derived their ancestry not from Rurik, but from another Scandinavian warlord, Rogvolod, who was believed to rule in Polotsk in the middle of the X century. Rogvolod was killed by Vladimir the Great in 978, and his only child - Rogneda - was taken by Vladimir as concubine. The conquered prinicipality has not been integrated into the unified Rus. Instead, Vladimir put his and Rogneda's son - Iziaslav - on the throne. Folllwing Vladimir's death in 1015, Iziaslav's son, Briachislav, proclaimed sovereignity, thus restoring his great-grandfather's state.
Yaroslav's death meant that the last direct threat to Polotsk's sovereignity has vanished. But did it mean a period of peace and stability for the restored principality?
Vseslav II Briachislavich "the Wise" (1044 - 1102)
1.1: Polotsk among other Russian principalities
Vseslav II was born as the only child of prince Briachislav. He was only 14 when he took the throne. Written accounts about his early life are very scarce, with the most commonly known piece coming from Nestor's Primary Chronicle:
And in the same year  died Briachislav, son of Iziaslav, grandson of Vladimir, father of Vseslav, and his son Vseslav sat on his throne, his mother bore him using sorcery. When his mother bore him, he had a язвено (yazveno) on his head, and his mother was told: "Put this язвено on him, let him carry it until death" And Vseslav carries it until today; that is why he does not care about bloodshed.
This short note sparked several interesting assumptions. The most popular one was that Vseslav was in fact a sorcerer, using magic and dark arts to deal with political opponents. One popular legend even says that Vseslav was capable of transforming himself into a wolf and that in such form he roamed his lands, spreading fear and satisfying his bloodlust.
Regardless of such rumors, one cannot deny the overally positive outcome of the first two decades of Vseslav's rule. Written documents indicate an intensive correspondence between the court at Polotsk and other grand centres of the Christian world - Constantinople, Kiev, Rome or Paris. Economically, control over the important waterway of Dvina made trade flourish, turning towns like Vitebsk and Dvinsk (Baltic Daugavpils) into major centres of commerce and artisancraft.
The Polotskian branch of the Rurikovich dynasty
Vseslav's five sons were married into several major European dynasties, furthering the political influence of the restored principality. In 1069, Vseslav's oldest son and heir, Gleb married Ingerid, the daughter of the Danish king Svend II - thus forging a short-lived, yet fruitful alliance against the Baltic pagans. Vseslav's other daughters-in-law came from Greek nobility - in 1071 Roman married Theophano Phokas, in 1076 Davyd married Sophia Komnena, in 1081 Sviatoslav married Anna Doukas and finally in 1082 Rogvolod married Beatrice of Chaldea. Thus, the Polotskian branch of the Rurikovich dynasty became tied with doukes of Charsianon, Armeniacon, Nicaea and Chaldea respectively. The reinforced ties with Constantinople were a mixed blessing, however; the brides brought with them respected scholars and theologians, who however in turn brought not only valuable tomes of wisdom and faith, but the seed of Monophysitist heresy as well.
Politically speaking, Vseslav's rule can hardly be considered a peaceful one. Encouraged by Svend II's crusade against the Baltic pagans, prince Vseslav made an energetic dash towards Dvina's estuary. Between 1067 and 1080, four campaings against the Balts took place. The principality annexed the region between the Dvina estuary and the western coast of the Chud lake. The last campaign of 1080 brought the conquest of isles Saaremaa and Hiiumaa, effectively securing the Dvina-Baltic trade route. One should note, however, that the war against the pagans was by no means easy; during the very first campaign of 1067-1068 the Lithuanians, acting as allies to defending Latgalians, invaded Polotsk and attempted to lay siege upong the capital city. The Russian army, led by boyar Matvei, managed to intercept them en route, thus repelling the invasion. The fall of Latgalian strongholds later that year meant the end of the war, preventing the pagans' return.
As of relations with the other Russian prinicpalities, Vseslav realised that anyone controlling Kiev and dominating the former domain of Yaroslav the Wise will soon become a direct threat to Polotsk as well. Thus, Vseslav intervened into Rurikovichs' internal struggles several times, always supporting the seemingly losing side. He was also active during wars against the nomadic Cumans, although his role was ambiguous, at best.
In 1070, Kievan prince Iziaslav Yaroslavich asked for Vsevolod's help against Vsevolod Yaroslavich, the prince of Rostov, and his Yatvingian allies. The war ended in 1073, with both the Rostovians and Yatvingians defeated by the Kievo-Polotskian coalition. The decisive battle was the battle of Novogrudok in April 1071; the Polotskian forces, led by Vseslav himself and aided by the Pecheng mercenaries, managed to defeat the core of Yatvingian army, thus opening the way towards pagan strongholds south of Neman river.
Peace was not long, however; when Iziaslav and Vseslav marched towards Tver and Rostov, the pagan Pechengs invaded Iziaslav's lands from the south. The nomads quickly advanced north, pillaging the belt of land from Torki to Turov, and crossed the Pripyat river, thus invading Vseslav's domain. In October 1073, the hastly mustered Polotskian forces attempted to stem the tide near the town of Borisov, but have been soundly defeated. Luckily for Vseslav, the nomads did not attempt to advance further north; instead they retuned to the southern bank of Pripyat, continuing their march across the steppe.
The battle of Borisov marked an end to the first period of Polotskian activity in relations with the Yaroslaviche (descendents of Yaroslav the Wise).
The second period began in 1082, when the war erupted between Iziaslav and the Sviatoslav Yaroslavich, prince of Ryazan and future tsar of Bulgaria. Vseslav once again pledged his support to Iziaslav. The war ended as fast as it began, though; within less than a month Iziaslav died, and his son Ingvar bargained a peace between his realm and Ryazan. This allowed Sviatoslav to concentrate on the eastern direction, furthering the conquest of Bulgaria. Ryazanian forces have not been stopped even by the seemingly overwhelming Cumans. Although the nomads managed to plunder several towns and even get as far as the city of Smolensk, they failed to break Sviatoslav's power.
Four years after Iziaslav's death, Vseslav switched sides and attempted to intervene on behalf of a rebellious noble, boyar Alexandr of Korsun, who attempted to overthrow prince Ingvar. However, before Vseslav forces could have been mustered, Ingvar managed to capture Alexander and sieze Korsun, preventing Polotskian direct interference.
A second chance to weaken the southern neighbour appeared in 1089, when princess Darya of Galich took up arms and declared independence from Ingvar's domain. Ingvar's forces, still spread thin after Alexandr's rebellion and yet another war with the Pechengs, had little chance of resisting a double assault; in 1091, Ingvar accepted Darya's terms, with Vseslav becoming a guarantor of peace.
Sources indicate that Vseslav did not limit himself to warfare and open politics. Chronicler Prokop from Kiev Pechersk Lavra mentioned the following in the beginning of the XII century:
Vseslav Briachislavich, a sorcerer and fearsome warrior, feared his enemies even in his sleep, even if they were far away. And since many enemies he had, his fear was great and sharp as a sword. Many venerable christians in Polotsk have seen dark fumes and flames spitting out of Vseslav's residence at night. And the fumes spread throughout Russia and killed his enemies. Thus died prince Iziaslav Yaroslavich in Kiev in 1082, and Mstislav Iziaslavich in Novgorod in 1085, and Sviatoslav Yaroslavich in 1101, the tsar of Bulgaria
Putting accusations of sorcery aside, one cannot doubt that Vseslav might have employed some behind the scenes techniques to dispose of potential enemies and rivals. Izisalav's death is a well established fact - he died of natural reasons, peacefully in his sleep, with his sons accompanying him in his quarters. Mstislav and Sviatoslav's deaths seem far more suspicious, however. Especially Sviatoslav's case is worth noting; the newly crowned tsar of Bulgaria, conqueror of the so-called Kama Bulgars and perhaps the most renewed Rurikovich of his time, was captured by the Cumans during a campaign of 1099. He spent two years as Cuman prisoner and died during an attempted jailbreak, reportadely shot with a bow to his back. Potential Vseslav's involvement has never been proved, although, taking into account that Sviatoslav was succeded by underage Yemelian Sviatoslavich, such weakening of the Bulgarian state would indeed serve Vseslav's interests well.
Finally, it should be noted that Vseslav was incapable of preventing two events that put Polotsk in an uneasy situation. First, the so-called Hungarian Norhtern Crusade of 1090-1092 resulted in Novgorod and Lithuania being integrated into the Arpads' kingdom. Second, a simultaneous campaign of prince Vladimir of Rostov against the Samoyed pagans and the following integrations of their vast territory greatly increased the principality's potential. By the end of XI century, he started styling himself "the tsar of Rus'". Thus, three large entities appeared north and east of Polotsk. But it was a threat the aging Vseslav could not fight with. He died in September 1102, aged 72 years old, after almost 60 years of reign.
The political map of northeastern Europe in 1102, the year of Vseslav II's death