Represi Stalinis di Mongolia
Penindasan Hebat

Selama tiga tahun berikutnya, mentor Soviet di Kementerian Dalam Negeri membimbing Choibalsan dalam merencanakan dan melaksanakan pembersihan yang akan datang. Di bawah arahan pawangnya Soviet, Chopyak, Choibalsan membuat aturan Komite Urusan Internal diubah pada Mei 1936 untuk memfasilitasi penahanan politisi berpangkat tinggi tanpa terlebih dahulu berkonsultasi dengan atasan politik. Segera setelahnya 23 lama berpangkat tinggi ditangkap karena berpartisipasi dalam "pusat kontra revolusioner." Setelah persidangan selama setahun, mereka dieksekusi secara terbuka pada awal Oktober 1937. Ketika Jaksa Agung Mongolia memprotes penuntutan para lama, dia juga ditangkap dan kemudian ditembak.
Pada bulan Agustus 1937, Marshal Demid yang berusia 36 tahun, yang popularitasnya selalu dibenci Choibalsan, meninggal dalam keadaan yang mencurigakan yang mengakibatkan promosi Choibalsan menjadi peran ganda Panglima Tertinggi militer dan Menteri Pertahanan Mongolia. Hari berikutnya Choibalsan, sebagai Menteri Dalam Negeri, mengeluarkan Perintah 366 yang menyatakan bahwa banyak orang di Mongolia "telah jatuh di bawah pengaruh mata-mata dan provokator Jepang." Pada bulan yang sama Stalin, yang dikhawatirkan oleh gerakan militer Jepang di Manchuria memerintahkan penempatan 30.000 pasukan Tentara Merah di Mongolia dan telah mengirim delegasi besar Soviet ke Ulaanbaatar di bawah Wakil Soviet NKVD Commissar Mikhail Frinovsky. Frinovsky ditugaskan menggerakkan pembersihan kejam yang telah dilakukannya dengan sangat efektif di Uni Soviet di bawah Kepala NKVD Nikolai Yezhov. Bekerja melalui penasihat Soviet yang telah tertanam di dalam Kementerian Dalam Negeri dan dengan Choibalsan yang patuh memberikan penutup simbolis, Frinovsky membangun kerangka pembersihan dari belakang layar; membuat daftar penangkapan dan menyusun "Komisi Darurat", sebuah gaya NKVD Troika (dipimpin oleh Choibalsan) untuk mengadili dan menghukum tersangka secara ekstra-yudisial.
Penangkapan 65 pejabat tinggi pemerintah dan intelejen pada malam 10 September 1937 menandakan peluncuran pembersihan dengan sungguh-sungguh. Semua dituduh memata-matai untuk Jepang sebagai bagian dari komplotan Genden-Demid dan sebagian besar mengaku di bawah siksaan hebat. Persidangan pertunjukan pertama diadakan di Teater Pusat Ulaanbaatar dari 18 hingga 20 Oktober 1937. 13 dari 14 orang yang dituduh dijatuhi hukuman mati.
Dalam ajang kekerasan yang berlangsung hampir 18 bulan, troika Choibalsan menyetujui dan melaksanakan eksekusi lebih dari 18.000 lama kontra-revolusioner. Para bhikkhu yang tidak dieksekusi diwajibkan masuk ke dalam angkatan bersenjata Mongolia  sementara 746 biara di negara itu dilikuidasi. Ribuan lebih intelektual oposisi, pejabat politik dan pemerintah berlabel "musuh revolusi," serta etnis Buryat dan Kazakh juga ditangkap dan dibunuh. 25 orang dari posisi teratas dalam partai dan pemerintah dieksekusi, 187 dari kepemimpinan militer, 36 dari 51 anggota Komite Sentral. Mengikuti model Rusia, Choibalsan membuka gulag di pedesaan untuk memenjarakan para oposisi. Sementara NKVD secara efektif mengelola pembersihan dengan mengadakan uji coba pertunjukan dan melaksanakan eksekusi, Choibalsan sering mabuk  kadang-kadang hadir selama penyiksaan  dan interogasi terhadap orang-orang yang dicurigai kontrarevolusioner, termasuk teman-teman lama dan kawan-kawannya. Perintah eksekusi NKVD Choibalsan yang dicap karet dan terkadang eksekusi yang diarahkan secara pribadi. Dia juga menambahkan nama-nama musuh politik ke daftar penangkapan NKVD hanya untuk menyelesaikan masalah lama. Namun demikian, bahkan ketika ia berusaha untuk menyelamatkan korban dengan merekomendasikan keringanan hukuman dalam kasus-kasus tertentu, petugas NKVD sering mengesampingkan keputusannya.