Josef Stalin
mengkhawatirkan kemungkinan akan terjadinya upaya pembunuhan dan kemudian meningkatkan keamanan pribadinya, termasuk dengan memperoleh penjagaan secara ketat sepanjang waktu dan dengan jarang muncul di muka umum.
Pembunuhan Kirov disusul oleh intensifikasi penindasan oleh negara; Stalin mengeluarkan sebuah dekret yang mendirikan troika NKVD yang dapat mengeluarkan putusan tanpa melibatkan pengadilan. Seperti halnya kebijakan de-kulakisasi yang ingin membersihkan daerah pedesaan dari pasukan anti-pemerintah, Stalin ingin melakukan hal yang sama di kota-kota. Pada tahun 1935, NKVD
diperintahkan untuk mengusir orang yang diduga anti-revolusi, terutama mereka yang pernah menjadi seorang aristokrat, tuan tanah, atau pengusaha sebelum terjadinya Revolusi Oktober. Pada bulan-bulan awal tahun 1935, lebih dari 11000 orang diusir dari Leningrad untuk ditempatkan di wilayah pedesaan yang terisolasi. Pada tahun 1936, Nikolai Yezhov menjadi kepala NKVD dan mengawasi
intensifikasi penindasan. Stalin sendiri-lah yang mendorong intensifikasi penindasan ini, yang berakar dari dorongan psikologisnya dan logika dari sistem yang telah ia dirikan, yaitu sistem yang memprioritaskan keamanan di atas segalanya.
Stalin mendalangi penangkapan banyak orang yang pernah menjadi lawannya di Partai Komunis: mereka dikutuk sebagai tentara bayaran yang didukung oleh Barat, dan banyak yang dipenjara atau diasingkan secara internal. Pengadilan Moskwa pertama (yang merupakan sebuah pengadilan bohong-bohongan) diadakan pada Agustus 1936. Kamenev dan Zinoviev adalah dua dari beberapa orang yang dituduh merencanakan pembunuhan. Mereka
berdua kemudian dinyatakan bersalah dan akhirnya dihukum mati. Pengadilan Bohong-Bohongan Moskwa kedua diadakan pada Januari 1937, dan yang ketiga pada Maret 1938; dalam pengadilan ketiga, Bukharin dan Rykov dituduh terlibat dalam rencana teroris Trotsky-Zinoviev dan kemudian dihukum mati. Pada akhir tahun 1937, seluruh sisa kepemimpinan kolektif
sudah hilang dari Politbiro, yang telah dikendalikan sepenuhnya oleh Stalin. Terjadi pengusiran massal dari partai, dan Stalin juga memerintahkan partai-partai komunis di luar negeri agar mereka membersihkan partai mereka dari unsur-unsur anti-Stalinis.
Pada tahun 1930-an dan 1940-an, kelompok NKVD membunuh para pembangkang dan oposisi di luar negeri; pada Agustus 1940, Trotsky dibunuh di Meksiko, sehingga menyingkirkan lawan terakhir Stalin di kalangan bekas pemimpin Partai. Pada bulan Mei, tindakan ini disusul oleh penangkapan sebagian besar anggota Komando Tertinggi Militer dan penangkapan massal anggota-anggota militer, seringkali berdasarkan
tuduhan yang dikarang-karang. Pembersihan tersebut menggantikan sebagian besar anggota lama partai dengan para pejabat yang lebih muda yang tidak mengenal masa sebelum kepemimpinan Stalin dan dianggap lebih setia dengannya. Petugas-petugas partai siap melaksanakan perintah yang diperoleh dan mencoba mengambil hati Stalin agar mereka tidak menjadi korban pembersihan.
Petugas-petugas ini seringkali melakukan penangkapan dan penghukuman mati yang jumlahnya melebihi kuota yang ditetapkan oleh pemerintahan pusat Stalin.
Penindasan semakin menguat pada Desember 1936 dan masih tetap dilancarkan dengan sangat intensif sampai November 1938, dan periode ini dikenal dengan julukan Pembersihan Besar-Besaran. Menjelang akhir tahun 1937, pembersihan tersebut sudah dilancarkan di luar partai dan juga berdampak terhadap warga. Pada Juli 1937, Politbiro memerintahkan pembersihan "unsur-unsur anti-Soviet" dalam masyarakat, yang berdampak
terhadap kaum Bolshevik yang menentang Stalin, mantan anggota kelompok Menshevik, serta anggota Partai Revolusioner Sosialis, pendeta, bekas prajurit Tentara Putih, dan penjahat pada umumnya. Pada bulan tersebut, Stalin dan Yezhov menandatangani Perintah No. 00447, yang mencantumkan nama 268950 orang untuk ditangkap, dan 75950 di antaranya dihukum mati. Ia juga melancarkan "operasi-operasi
nasional", yaitu pembersihan terhadap kelompok etnis non-Soviet-beberapa diantaranya adalah orang Polandia, Jerman, Latvia, Finlandia, Yunani, Korea, dan Tionghoa-melalui pengasingan internal atau eksternal. Pada tahun-tahun tersebut, sekitar 1.6 juta orang ditangkap. 700000 orang ditembak, dan sejumlah orang yang tidak diketahui jumlahnya tewas akibat penyiksaan oleh NKVD.
Stalin memprakarsai semua keputusan penting pada masa Teror tersebut, secara pribadi mengarahkan operasi-operasinya dan memperhatikan rincian-rincian implementasinya. Motif Stalin masih diperdebatkan di kalangan sejarawan. Menurut Khlevniuk, tulisan-tulisan pribadinya dari masa itu "sangat membelit dan tidak koheren", yang diisi dengan klaim mengenai persekongkolan dan musuh-musuh di
sekelilingnya. Ia sangat khawatir dengan keberhasilan pasukan sayap dalam melengserkan pemerintahan sayap di Spanyol, yang membuatnya gelisah terhadap unsur-unsur anti-Stalinis domestik yang dianggap dapat menjadi kolom kelima dalam peristiwa perang mendatang dengan Jepang dan Jerman. Teror Besar berakhir setelah Yezhov dicopot dari jabatan kepala NKVD dan digantikan oleh
Lavrentiy Beria, orang yang benar-benar setia dengan Stalin. Yezhov ditangkap pada April 1939 dan dihukum mati pada tahun 1940. Teror tersebut telah merusak reputasi Uni Soviet di luar negeri, terutama di kalangan sayap yang sebelumnya menjadi simpatisan, dan saat teror ini mereda Stalin mencoba melempar tanggung jawab. Ia kemudian mengklaim bahwa "tindakan berlebihan" dan "pelanggaran hukum" selama teror tersebut merupakan kesalahan Yezhov.
Sebagai seorang Marxis-Leninis, Stalin memperkirakan akan terjadi Perang Dunia Kedua di antara negara-negara kapitalis. Saat Jerman Nazi menguasai Austria dan kemudian sebagian wilayah Cekoslowakia pada tahun 1938, Stalin menyadari bahwa perang tersebut akan segera dimulai. Ia ingin Uni Soviet bersikap netral selama konflik tersebut dengan harapan agar perang Jerman melawan Prancis dan Britania Raya akan menyisakan
Soviet sebagai kekuatan yang dominan di Eropa. Dari sudut pandang militer, Uni Soviet juga menghadapi ancaman dari timur, yaitu Kekaisaran Jepang, dan pasukan Soviet sempat bentrok dengan Jepang pada Mei 1939. Stalin pun memulai program pembangunan kekuatan militer dan jumlah anggota Tentara Merah berlipatganda antara Januari 1939 dan Juni 1941, meskipun banyak perwira yang tidak memperoleh pelatihan yang baik akibat proses perekrutan yang terburu-buru.
Saat Britania Raya dan Prancis tampak enggan bersekutu dengan Uni Soviet, Stalin merasa bahwa ia dapat membuat kesepakatan yang lebih menguntungkan dengan Jerman. Pada Mei 1939, Jerman memulai perundingan dengan Soviet dan mengusulkan agar mereka membagi-bagi wilayah Eropa Timur. Stalin memandangnya sebagai kesempatan untuk memperluas wilayah dan juga untuk memelihara perdamaian dengan Jerman. Pada Agustus
1939, Uni Soviet menandatangani pakta non-agresi dengan Jerman, yang dirundingkan oleh Menteri Luar Negeri Soviet Vyacheslav Molotov dan Menteri Luar Negeri Jerman Joachim von Ribbentrop. Sepekan kemudian, Jerman menyerbu Polandia, sehingga Britania Raya dan Prancis menyatakan perang terhadap Jerman. Pada tanggal 17 September, Tentara Merah memasuki wilayah timur Polandia; alasan resminya adalah untuk mengembalikan
ketertiban saat negara Polandia sedang mengalami keruntuhan. Alasan ini dirancang agar tidak membuat murka Britania Raya dan Prancis.
Stalin mengusulkan pertukaran wilayah dengan Jerman. Ia akan memberikan kepada Jerman daerah yang didominasi oleh etnis Polandia dan sebagian wilayah Provinsi Warsawa, dan sebagai gantinya Uni Soviet akan memperoleh wilayah Lituania, karena Stalin ingin menggabungkan kembali ketiga negara Baltik dengan Uni Soviet. Usulan ini disepakati pada tanggal 28 September. Perjanjian Perbatasan Jerman-Soviet ditandatangani tak
lama sesudahnya di tengah kehadiran Stalin. Kedua negara tersebut juga meneruskan hubungan dagang, sehingga mengurangi dampak blokade Britania Raya terhadap Jerman.