Berita hoax sangat mudah tersebar di internet dan sosial media. Hal tersebut terjadi karena minimnya pengetahuan pengguna internet dan sosial media mengenai ciri-ciri berita hoax. Tujuan penelitian ini adalah mengimplementasikan teknik clustering K-Nearest dan K-Means. Dimana K-Means sendiri berfungsi untuk mengurangi waktu komputasi pada proses pengelompokan dokumen berita hoax berbahasa Indonesia denagn metode K-Nearest Neighbor. Adapun teknik pengumpulan data yang dilakukan 1) Studi Pustaka, 2) Melalui situs website Kemkominfo RI dan kompas.com. Data tersebut dianalisis dengan menggunakan kombinasi K-Nearest Neighbor dan K-Means. Hasil penelitian ini menunjukkan bahwa K-Means dapat mengurangi waktu komputasi pada pengelompokan hoax berita dengan metode K-Nearest Neighbor dibandingkan dengan metode K-Nearest Neighbor murni. Rata-rata waktu komputasi metode K-Nearest Neighbor dan K-Means adalah 0,041 detik, sedangkan waktu komputasi metode K-Nearest Neighbor murni adalah 2,390 detik. Dengan tingkat akurasi tertinggi sebesar 97,7% pada metode usulan, sedangkan K-Nearest Neighbor murni tingkat akurasinya hanya mencapai 89,20%. Kesimpulan dari hasil penelitian ini adalah metode yang diusulkan yaitu algoritma K-Nearest Neighbor dan K-Means. Mampu melakukan klasifikasi berita hoax, sedangkan untuk algoritma K-Means sendiri mampu mengurangi waktu komputasi pada algoritma K-Means.