După abolirea monarhiei în februarie 1917, Rusia era în debandadă totală. Înfrângerile militare au determinat erodarea încrederii în Guvernul Provizoriu şi venirea la putere, prin forţa armelor, a partidului bolşevic. La o lună şi jumătate de la lovitura de stat de la Petrograd, Lenin a înţeles că are nevoie de o structură puternică care să lupte împotriva duşmanilor revoluţiei, dar şi a tuturor care pun la îndoială într-un fel sau altul legitimitatea noii puteri. Anterior, funcţia luptei împotriva inamicilor puterii bolşevice era îndeplinită de Comitetul militar-revoluţionar.
Acesta a fost desfiinţat şi în locul său s-a creat în 20 (7) decembrie 1917 Comisia Extraordinară din toată Rusia pentru lupta împotriva contrarevoluţiei şi sabotajului, VCK sau CEKA, cum avea să intre în istorie. Preşedinte al acestuia a fost numit Felix Djerjinski, un bolşevic de origine poloneză, om de încredere a lui Lenin. Iniţial, în componenţa conducerii CEKA au intrat şi membri ai partidului eserilor de stânga, un partid cu o pondere importantă în rândurile ţăranilor, pe care bolşevicii i-au cooptat la putere pentru a proiecta ideea unei coaliţii de guvernare. Când aceştia s-au opus unor măsuri luate de bolşevici, inclusiv în ceea ce priveşte represiunea politică, Lenin a decis eliminarea fizică a liderilor principali ai eserilor de stânga prin intermediul CEKA.
Din februarie 1918, CEKA-ul obţine dreptul de a dispune de viaţa deţinuţilor şi a tuturor celor care erau percepuţi drept inamici ai regimului bolşevic. Este începutul neoficial al terorii roşii, pe care bolşevicii o lansează în 5 septembrie 1918 după atentatul eşuat la viaţa lui Lenin şi asasinarea lui Uriţki, şeful CEKA de la Petrograd.
Drept ţintă principală a poliţiei politice bolşevice, predecesoare a KGB-ului, erau aşa numiţii byvshie, adică cei care erau consideraţi oameni ataşaţi vechiului regim: funcţionari publici, ofiţeri, bancheri, proprietari de prăvălii, negustori, latifundiari etc.
Este adevărat că unii dintre aceştia au fost cooptaţi în CEKA, mai ales foşti ofiţeri în armata ţaristă, dar marea lor majoritatea a fost ostracizată sau exterminată. Cooptarea unora din byvshie în CEKA a servit ulterior puterii sovietice să dea vină pe aceştia atunci când se auzeau voci despre cruzimea cekiştilor şi uciderea unor oameni nevinovaţi. Cu alte cuvinte, aceştia făceau special în aşa fel încât să compromită puterea bolşevică în rândurile maselor populare.
În realitate însă, Lenin şi majoritatea liderilor comunişti, cu excepţia notabilă a lui Kamenev, susţineau întărirea prerogativelor discreţionare ale CEKA şi invocau necesitatea aplicării terorii fără un proces de judecată. În acest sens, CEKA era un organ care în mod formal avea dreptul de a reţine şi efectua o anchetă preliminară a suspecţilor, practic însă acesta îşi aroga şi funcţia de procuratură şi judecătorie.
CEKA s-a transformat astfel în organ extrajudiciar, un instrument atotputernic al terorii. Numai în două luni de zile, septembrie-octombrie 1917, CEKA a executat cca. 15 mii persoane. Era o cruzime neîntâlnită sub vechiul regim: în ultimii o sută de ani de ţarism au fost condamnaţi la moarte din motive politice cca. 6 400 de persoane, dintre care o treime a fost executată în timpul revoluţiei din 1905-1907.
Chiar înaintea începutului războiului civil şi a terorii roşii, au fost executaţi mii de muncitori, adică reprezentanţi ai clasei pentru care oficial bolşevicii preluaseră puterea. Muncitorii au fost omorâţi dat fiind că au îndrăznit să participe la demonstraţii stradale pentru a denunţa terorismul noii puteri bolşevice, cerând instaurarea unei veritabile democraţii, a sovietelor, dar fără bolşevici.
Din cauza atrocităţilor comise, CEKA a căpătat denumirea în popor de „noua ohrancă”. Teroarea aplicată de poliţia politică, de CEKA, transformată ulterior în GPU, NKVD, MGB şi în cele din urmă în KGB, va fi unul din factorii principali care va permite regimului comunist să se perpetueze 7 decenii la rând, cu preţul a milioane de vieţi omeneşti, printre care şi a sute de mii de moldoveni.
