Kata Polotesk dalam bahasa Slav Timur Lama berasal dari nama Sungai Polota (arti sebenarnya adalah Puolauta yang dalam bahasa Lithuania berarti 'terjatuh ke' seperti misalnya sungai yang mengalir ke sungai yang lebih besar), yang mengalir ke Sungai Dvina Barat. Bangsa Viking menyebutnya sebagai Palteskja.
Polotsk merupakan salah satu kota berumur panjang di Slav Timur. Hikayat Awal (Повѣсть времяньныхъ лѣтъ, Povest' Vremyan'nykh Let), kitab yang menceritakan sejarah Kievan Rus', menyebutkan Polotsk pada tahun 862 (dengan nama Полотескъ, /poloteskŭ/), bersama dengan Murom dan Beloozero. Terdapat perdebatan mengenai hal ini. Beberapa sejarawan percaya Polotsk belum terbentuk atau belum eksis pada abad ke-9 Masehi sehingga catatan tersebut merupakan rekaan dari penyusun kitab.[7] Namun, sebuah penelusuran arkeologi dari Institut Sejarah Akademi Ilmu Pengetahuan Nasional Belarus menyebutkan bahwa Polotsk ada pada paruh pertama dari abad ke-9 Masehi.[8]Saga Norwegia menggambarkan Polotsk sebagai kota dengan benteng yang sangat kuat di seluruh Rus.
Sepanjang abad ke-10 dan 12 Masehi, Kepangeranan Polotsk muncul sebagai titik pusat kekuasaan yang dominan yang sekarang berada dalam daerah Belarus, dengan beberapa bantuan oleh Kepangeranan Turov di selatan. Kepangeranan menegeaskan kedaulatannya dalam hubungan dengan pusat-pusat Kievan Rus lainnya, menjadi ibu kota politik, dan episkopat serta pemimpin dari daerah-daerah bawahan (vassal) di Balt di barat. Salah satu pangeran terkemukanya ialah Pangeran Vseslav Bryachislavich, yang memangku tahta dari tahun 1044 hingga tahun 1101. Catatan dari abad ke-12 yang diperintahkan pembuatannya oleh putra Vseslav, Boris, dapat dilihat pada batuan-batuan besar di dekat Katerdal Santa Sofia.
Pada tahun 1240, Polotsk menjadi negara bawahan dari pangeran-pangeran Lithuania. Adipati Agung Lithuania, Vytenis, merebut kota tersebut lewat pertempuran militer pada tahun 1307, menyelesaikan apa yang telah dimulai oleh pangeran-pangeran Lithuania sebelumnya pada tahun 1250-an.[9] Polotsk memperoleh sebuah perjanjian otonomi, menjamin bahwa adipati agung ′tidak akan menerapkan hal-hal baru, tidak pula menghilangkan hal-hal lama′.[10] Polotsk menjadi yang pertama untuk bisa tergabung ke Keadipatian Agung Lithuania.[10] Dengan hal ini, Lithuania telah berhasil secara nyata mengendalikan jalur perdagangan Dvina di tangannya, mengamankan sebuah unsur penting bagi kegiatan perekonomian di sekitarnya.[9]Hukum Magdeburg disahkan penggunaannya pada tahun 1498. Polotsk menjadi ibu kota dari Kevoivodan Połock dalam Persemakmuran Polandia-Lithuania hingga tahun 1772. Setelah direbut oleh Russia di bawah Ivan Sang Pengacau pada tahun 1563, Polotsk dikembalikan kepada Keadipatian Agung Lithuania 15 setelahnya.
Ikon kebudayaan dari abad pertengahan di antaranya adalah karya dari biarawati Eufrosyne dari Polatsk (1120–1173), yang membangun biara, menulis kitab-kitab, mendukung pendidikan membaca dan menulis serta kesenian (termasuk seniman lokal Lazarus Bohsha dengan karya terkenalnya "Salib Santa Euphrosyne," lambang kenegaraan dan benda berharga yang hilang dalam Perang Dunia II), serta ceramah dan tulisan dari Uskup Gereja Slavonia, Cyril dari Turaw (1130–1182).
Ahli percetakan pertama Belarus, Francysk Skaryna, lahri di Polotsk sekitar tahun 1490. Ia terkenal dari keberhasilannya untuk pertama kali mencetak Alkitab dalam bahasa Belarus Lama tahun 1517.
Pada bulan September 2003, "Hari Melek Akasaara Belarus" dirayakan untuk kesepuluh kalinya di Polotsk. Pemerintah kota memutuskan untuk membangun monumen untuk huruf Kiril Belarus "Ў", yang tidak digunakan di bahasa Slav lainnya. Ide dari pendirian monumen berasal dari ahli kaligrafi Belarus, Paval Siemchanka, yang telah beberapa tahun mempelajari aksara Kiril.
^ abThe New Cambridge Medieval History: c. 1300-c. 1415. p.706
^ abThe New Cambridge Medieval History: c. 1300-c. 1415. pp.769-770
^Savelyev, Yu. R. Vizantiysky stil v architecture Rossii (Савельев, Ю. Р. Византийский стиль в архитектуре России. - СПБ., 2005) Saint Petersburg, 2005. ISBN 5-87417-207-6, p.260