Transisi ke Orde Baru
Runtuhnya sistem Demokrasi Terpimpin > Pembersihan berdarah anti-komunis

Artikel utama: Pembantaian di Indonesia 1965-1966
Pada awal Oktober, kampanye propaganda militer mulai menyapu Indonesia, dan berhasil meyakinkan baik masyarakat Indonesia dan internasional bahwa peristiwa Gerakan 30 September adalah sebuah "kudeta Komunis", dan bahwa pembunuhan jenderal faksi sayap kanan TNI tersebut adalah kekejaman pengecut terhadap para pahlawan Indonesia. Dalam kampanye tersebut, Gerakan 30 September disebut "Gestapu" (dari "Gerakan September Tigapuluh"). Tentara, bertindak atas perintah Soeharto dan diawasi oleh Nasution, memulai kampanye agitasi dan hasutan untuk melakukan kekerasan berdarah di kalangan warga sipil Indonesia yang ditujukan untuk masyarakat pendukung dan simpatisan ideologi Komunis, dan bahkan terhadap Presiden Soekarno sendiri. Penyangkalan PKI tentang keterlibatan mereka dalam G30S memiliki pengaruh yang kecil. Rezim Soekarno dengan cepat menjadi tidak stabil, dengan Angkatan Darat menjadi satu-satunya kekuatan yang tersisa untuk menjaga ketertiban.
Pada pemakaman Ade Irma, putri Nasution yang meninggal dalam peristiwa G30S, Komandan Angkatan Laut Laksamana Martadinata memberi sinyal pada para ulama dan pemimpin Muslim untuk menyerang Komunis. Pada tanggal 8 Oktober, kantor pusat PKI dijarah dan dibakar habis saat petugas pemadam kebakaran hanya berdiri diam. Mereka kemudian berdemonstrasi massal menuntut pembubaran Partai Komunis Indonesia. Rumah-rumah tokoh senior partai, termasuk ketua PKI D.N. Aidit, M.H. Lukman dan Nyoto juga dibakar. Tentara kemudian memimpin kampanye untuk membersihkan masyarakat Indonesia, pemerintah dan angkatan bersenjata dari elemen partai komunis dan organisasi massa berhaluan kiri lainnya. Para pemimpin dan anggota PKI segera ditangkap, beberapa langsung dieksekusi mati tanpa pengadilan apapun.
Pada tanggal 18 Oktober, sebuah deklarasi dibacakan melalui semua stasiun radio yang dikendalikan militer, menyatakan bahwa Partai Komunis Indonesia adalah partai terlarang. Larangan tersebut termasuk partai PKI sendiri dan semua "onderbouw"-nya (sayap organisasi) seperti organisasi pemuda dan perempuan, asosiasi petani, intelektual dan kelompok mahasiswa, dan serikat buruh SOBSI. Pada saat itu, tidak jelas apakah larangan ini hanya diterapkan terhadap Jakarta (yang saat itu dikuasai oleh TNI Angkatan Darat), atau seluruh Republik Indonesia. Namun, larangan itu segera digunakan sebagai dalih oleh Tentara Nasional Indonesia untuk pergi di seluruh Indonesia melaksanakan hukuman di luar hukum, termasuk penangkapan massal dan eksekusi kilat, terhadap siapapun yang dicurigai pendukung kelompok kiri atau komunis, dan loyalis Soekarno. Saat penyebaran kekerasan berdarah tersebut, Soekarno mengeluarkan perintah untuk mencoba menghentikannya, tetapi ia diabaikan. Dia juga menolak untuk menyalahkan PKI untuk peristiwa "kudeta" tersebut, apalagi melarangnya seperti yang dituntut oleh TNI Angkatan Darat. Namun, meski Soeharto dan Nasution semakin curiga tentang peran Soekarno dalam peristiwa itu, TNI Angkatan Darat enggan untuk menghadapi Soekarno langsung karena popularitasnya yang masih luas.
Dimulai pada akhir Oktober 1965, dan dipanas-panasi oleh kebencian masyarakat yang terpendam, TNI dan sekutu sipilnya ( terutama kelompok vigilante Muslim) mulai membunuhi orang-orang yang ada hubungan dengan PKI maupun onderbouw-nya, baik yang hanya diduga maupun yang memang betul. Pembunuhan dimulai di ibu kota, Jakarta, menyebar ke Jawa Tengah dan Jawa Timur, dan kemudian Bali. Meskipun pembunuhan terjadi di seluruh Indonesia, yang terburuk berada di kubu PKI Jawa Tengah, Jawa Timur, Bali, dan Sumatra utara. Pembantaian mencapai puncaknya selama sisa tahun 1965, sebelum mereda pada bulan-bulan awal tahun 1966. Perkiraan jumlah korban tewas dari berbagai kekerasan ini berkisar dari lebih dari 100.000 sampai 3 juta, namun kebanyakan sejarawan menerima figur sekitar 500.000. Banyak orang lain juga dipenjara dan selama sepuluh tahun ke depan, orang-orang masih ditangkap dan dipenjarakan sebagai tersangka. Diperkirakan bahwa sebanyak 1,5 juta orang dipenjarakan atas dasar dugaan pendukung komunisme pada satu saat pada masa tersebut. Sebagai hasil dari pembersihan tersebut, salah satu dari tiga pilar pendukung Soekarno, Partai Komunis Indonesia, telah secara efektif dihilangkan oleh dua lainnya, yaitu militer dan politik Islam.