This article explores the exchange of letters by Caucasus Muslims across the Russo-Ottoman border and the tsarist government's reactions to it. Between the 1850s and World War I, about a million Muslims left the Caucasus for the Ottoman empire. Many of them, especially Circassians, were expelled by the Russian army, and others, including Chechens, Abkhazians, and Daghestanis, were pushed out or emigrated under tsarist rule. Private letters sustained the Russo-Ottoman Muslim world, which included refugees, emigrants, and pilgrims. The letters, written in Arabic or Ottoman Turkish, were typically smuggled across the border and occasionally intercepted by Russian authorities. I argue that Muslims’ letters fueled the Russian government's paranoia about Pan-Islamism, or advocacy for Muslim unity, that purportedly threatened Russia's colonial project in the Caucasus. Russian officials interpreted the letters as pro-Ottoman propaganda, which underpinned tsarist suppression of transborder correspondence and mobility.