From 1868 to 1920, the Amirate of Bukhara was a legally independent country with a sovereign monarchy dating back to the mid-eighteenth century. During this same period, Bukhara was subject to colonial rule, in many ways functioning like other provinces of the Russian Empire. How can both of these statements be true simultaneously? This paper reconsiders sovereignty in colonial-era Bukhara through the prism of bureaucracy. It argues that the logic of the multi-confessional empire -- a broad paradigm that characterized both Russia and Bukhara -- allowed for the coexistence of nested forms of sovereignty such that Bukhara was both a constituent part of the Russian Empire and a sovereign Islamic state at the same time. This seeming paradox is clarified by following the paper trail both within Bukhara and in dialogue with Russian interlocutors, fueled by translation between linguistic registers and corresponding symbols of sovereignty.