With the Treaty of Küçük Kaynarca (1774), signed after the Russo-Ottoman war of 1768-1774, the Ottoman Empire lost the Crimean Khanate. It thus became nominally independent state and its first ruler was pro-Russian Şahin Giray. The new status of the Khanate was confirmed by the Aynalıkavak Agreement signed in 1779 between Russia and the Empire. As a ruler, Şahin Giray inaugurated a modernization process in the Khanate, but faced fierce opposition and a revolt started in 1782. Using the upheavel as a pretext, the Russians entered the Khanate and annexed it the following year. Being the first Muslim territory lost the enemy, it was a severe blow to the Ottomans. Thereafter, the Ottoman rulers tried to develop military and political strategies in the Caucasia to regain the Khanate. An important part of the military strategy was to build a fortress in Anapa, a strategically important place on the Russian frontier. Moreover, contacts were established with the local tribes with the aim of collaborating with them against the Russian threat. Focusing on the Anapa fortress, the aim of this paper is to study the military and diplomatic strategies employed in the Northern Caucasia by the Ottoman Empire to take back the Crimean Khanate from the Russians.