Setelah revolusi Oktober pada tahun 1917, Vladimir Lenin, terpilih sebagai pemimpin pertama negara USSR yang baru berdiri sebagai hasil dari revolusi tersebut. Dengan maksud ingin melakukan kontrol terhadap populasi, Lenin pun membentuk The Cheka. The cheka adalah sebuah singkatan dalam bahasa Rusia yang jika diterjemahkan kurang lebih berarti " Komisi darurat seluruh Rusia untuk perlawanan kontra revolusi dan sabotase." Pada masa perang sipil tahun 1918-1920, The Cheka, yang saat itu dipimpin oleh aristokrat polandia bernama Felix, telah menahan, menyiksa, dan mengeksekusi ribuan rakyat USSR. Pada masa ini, The cheka sering kali melakukan metode eksekusi yang berhasil menebarkan teror bagi rakyat yang melawan negara, yaitu dengan menembak dari jarak dekat ke bagian belakang kepala, di gang-gang gelap di Uni Sovyet. Dan pada tahun 1923, The Cheka pun bermutasi menjadi The OGPU. The OGPU adalah Direktorat politik gabungan dibawah naungan dewan rakyat USSR. The OGPU beroperasi pada periode yang relatif lancar dalam sejarah Soviet (tidak ada pembersihan besar-besaran, tidak ada deportasi internal terhadap jutaan etnis minoritas), namun badan inilah yang melakukan pembasmian terhadap hal-hal yang bersifat keagamaan di Sovyet. The OGPU juga dengan kejam menganiaya organisasi keagamaan (termasuk Gereja Orthodok Rusia) dengan alasan untuk membasmi pembangkang dan penyabot.
Tidak seperti lembaga-lembaga sebelumnya, NKVD (Komisariat Urusan Dalam Negeri) murni adalah gagasan Joseph Stalin. NKVD dibentuk pada waktu yang sama ketika Stalin mengatur pembunuhan Sergei Kirov, dengan alasan untuk membersihkan barisan teratas Partai Komunis dan menyerang teror ke dalam masyarakat. Dalam 12 tahun keberadaannya, dari tahun 1934 sampai 1946, NKVD menangkap dan mengeksekusi jutaan orang secara harafiah. Pada masa perebutan kekuasaan yang diikuti dengan kematian Stalin, menjadi kepala NKVD adalah suatu pekerjaan yang berbahaya: Genrikh Yagoda ditangkap dan dieksekusi pada tahun 1938, Nikolai Yezhov pada tahun 1940, dan Lavrenty Beria pada tahun 1953.

Setelah berakhirnya Perang Dunia II dan sebelum eksekusi, kepemimpinan Lavrenty Beria memang berjalan agak lamban dari segi perkembangan dan struktur organisasi. Pada masa ini, badan keamanan ini dikenal sebagai MGB (Kementerian Keamanan Negara), kadang-kadang sebagai NKGB (Komisariat Negara untuk Keamanan Negara), dan juga pernah disebut, selama perang, sebagai SMERSH. Dan setelah kematian Stalinlah akhirnya secara formal KGBterbentuk, atau Komitet Gosudarstvennoy Bezopasnosti (Komisariat untuk Keamanan Negara). Meskipun reputasinya yang menakutkan di barat, KGB sebenarnya lebih efektif dalam mengawasi Uni Soviet dan negara-negara satelit Eropa timur dibandingkan dalam mengobarkan revolusi di Eropa barat atau mencuri rahasia militer dari AS (Era keemasan spionase Rusia sebenarnya pada masa-masa menjelang berakhirnya Perang Dunia II, sebelum pembentukan KGB, ketika Uni Soviet berhasil menyabotase ilmuwan barat untuk memajukan pengembangan senjata nuklirnya sendiri). Prestasi luar negeri utama KGB termasuk menekan Revolusi Hungaria pada tahun 1956 dan "Musim Semi Praha" di Cekoslovakia pada tahun 1968, serta mendirikan sebuah pemerintahan Komunis di Afghanistan pada akhir 1970an; Namun, keberuntungan agensi tersebut berakhir pada awal tahun 1980an di Polandia, di mana gerakan Solidaritas anti-Komunis muncul dengan penuh kemenangan. Pada masa ini, CIA dan KGB sering terlibat dan berbenturan dalam operasi internasional yang rumit (seringkali di negara-negara dunia ketiga seperti Angola dan Nikaragua), yang melibatkan agen, agen ganda, propaganda, disinformasi, penjualan senjata di bawah meja, campur tangan dengan pemilihan, dan pertukaran koper malam hari yang dipenuhi rubel atau uang ratusan dolar. Rincian yang tepat tentang apa yang terjadi, dan di mana, mungkin tidak akan pernah terungkap; banyak agen dan "pengendali" dari kedua belah pihak telah tewas, dan pemerintah Rusia saat ini belum mengumumkan pengarsipan dari arsip KGB. Di Uni sovyet, sikap KGB terhadap penekanan perbedaan pendapat sebagian besar didikte oleh kebijakan pemerintah. Selama masa pemerintahan Nikita Khrushchev, dari tahun 1954 sampai 1964, sejumlah keterbukaan ditoleransi, seperti yang disaksikan dalam penerbitan memoar era Alexander Solzhenitsyn "One Day in the Life of Ivan Denisovich" (sebuah peristiwa yang tidak pernah terpikirkan di bawah rezim Stalin). Pengangkatan Leonid Brezhnev pada tahun 1964, dan, terutama, pemilihan Yuri Andropov sebagai kepala KGB pada tahun 1967 memberi warna lain bagi KGB. KGB milik Andropov membebaskan Solzhenitsyn dari Uni Soviet pada tahun 1974, dan umumnya membuat hidup sengsara untuk beberapa tokoh terkemuka bahkan sedikit tidak puas dengan kekuatan Soviet.

Pada akhir 1980-an - disebabkan karena perang yang menghancurkan di Afghanistan, dan sebagian lagi karena perlombaan senjata yang semakin mahal dengan A.S. - Uni Sovyet pun perlahan mulai berantakan, dengan inflasi yang merajalela, kekurangan barang pabrik, dan agitasi oleh etnis minoritas. Perdana Menteri Mikhail Gorbachev mulai menerapkan "perestroika" (sebuah restrukturisasi ekonomi dan struktur politik Uni Soviet) dan "glasnost" (sebuah kebijakan keterbukaan terhadap para pembangkang), namun sementara hal ini menenangkan beberapa penduduk, dilain sisi, hal tersebut juga membuat marah garis keras Birokrat Soviet yang sudah terbiasa dengan hak istimewa mereka. Dan seperti yang diperkirakan, KGB berada di garis depan kontra-revolusi. Pada akhir 1990-an, kepala KGB Vladimir Kryuchkov merekrut anggota elit Soviet yang berpangkat untuk menggerakkan sebuah aksi konspirasi, setelah gagal meyakinkan Gorbachev untuk mengundurkan diri demi kandidat yang diinginkan atau menyatakan negara dalam keadaan darurat. Pejuang bersenjata itu, beberapa di antaranya berada di dalam tank, menyerang gedung parlemen Rusia di Moskow, namun Presiden Soviet Boris Yeltsin memegang teguh dan kudeta tersebut pun gagal. Empat bulan kemudian, Uni sovyet pun dibubarkan secara resmi, memberikan otonomi kepada Republik Sosialis Soviet di sepanjang perbatasan barat dan selatan dan membubarkan KGB (beserta dengan semua badan pemerintah Soviet lainnya). Namun, institusi seperti KGB tidak akan pernah benar-benar pergi; mereka hanya menggunakan nama samaran yang berbeda. Saat ini, Rusia didominasi oleh dua badan keamanan, FSB (The Federal Security Service of the Russian Federation) dan SVR (The Foreign Intelligence Service of the Russian Federation), yang secara umum berhubungan dengan FBI dan CIA. Yang lebih mengkhawatirkan, adalah kenyataan bahwa Presiden Rusia Vladimir Putin menghabiskan 15 tahun di KGB, dari tahun 1975 sampai 1990, dan peraturannya yang semakin otokratis menunjukkan bahwa dia sepertinya menerapkan pelajaran yang dia pelajari di sana. Memang tidak mungkin penduduk Rusia lagi-lagi akan melihat agen keamanan yang bersikap bagaikan setan seperti NKVD, tapi kembalinya hari-hari tergelap seperti pada masa KGB jelas sesuatu yang tidak diharapkan.