The article examines the ways that historians think about the evidence they use in their accounts of Russian-Muslim relations. It focuses on a neglected type of source that reflects relations between tsarist officials and the peoples of the Caucasus – North Caucasus Turki letters exchanged between members of the native population and tsarist officials. The article considers the extent to which historians of Russian-Muslim encounters discuss primary sources in their work. It draws attention to and considers the consequences of historians’ neglect of Caucasus-related tsarist and Muslim diplomatics. Finally, the article examines an array of Turki letters for what they reveal about Russian-Muslim encounters in the North Caucasus between the seventeenth and twentieth centuries. The article argues that tsarist officials used correspondence in Turki to claim Caucasus Muslims as subjects. For their part, Caucasus Muslims used Turki to communicate their needs and wants to tsarist officials locally, regionally, and centrally, and to express their willingness to advance Russia’s interests as the tsar’s servants (qullar). The article concludes that tsarist officials and Caucasus Muslims often had compelling reasons to cultivate mutually beneficial relationships, and that their ability to do so, to overcome the myriad internal and external challenges to Russian-Muslim comity, helps to explain the longevity of Russian empire in the Caucasus.