This chapter examines the evolution of Russia's counter-terrorist operation in Chechnya and assesses the success of its attempts to deter terrorist activity. It argues that the Russian authorities, under the leadership of Boris Yeltsin, lacked credibility and capability in the eyes of the Chechens, meaning that they were unable to effectively deter Chechen separatists from pursing independence during the 1990s. In 1944 the Chechens became the largest group on a compact territory to be deported en masse by Stalin for alleged collaboration with the Nazis. The chapter focuses on an analysis of Russian denial and punishment strategies and their impact on challenges from terrorist groups in the North Caucasus. It argues that, although the use of excessive force demonstrated Russian resolve to counter terrorism, it initially undermined the credibility of the operation and boosted support for violent non-state actors.