It was situated in what is today Nenets Autonomous Okrug, about 20 km south-west of Naryan-Mar.
Pustozersk was founded in 1499 in the lower reaches of the Pechora River by Princes Semyon Kurbsky and Pyotr Ushaty.
Pustozersk was supposed to play the role of a military fort on the northern borders of the Russian state.
The town was most active in the 17th century, when such notable people as Artamon Matveyev, Vasily Galitzine, and Avvakum were exiled there.
In the 18th century, Pustozersk gradually lost its economic importance and began to deteriorate because a more convenient southern route to Siberia through the Urals had been discovered.