Pajak Bumi dan Bangunan (PBB) merupakan salah satu sumber utama Pendapatan Asli Daerah (PAD) yang berperan penting dalam mendukung pembangunan infrastruktur daerah. Namun, tingkat kepatuhan wajib pajak dalam membayar Pajak Bumi dan Bangunan di Kota Medan masih belum terlalu baik, terutama karena rendahnya kesadaran para wajib pajak. Untuk mengatasi solusi dari kepatuhan wajib pajak bumi dan bangunan digunakan proses Algoritma K-Means, yang dimana Algoritma K-Means dipilih karena kemampuannya dalam membagi data menjadi kelompok berdasarkan karakteristik tertentu. Penelitian ini bertujuan untuk mengelompokkan tingkat kepatuhan wajib pajak bumi dan bangunan di Kota Medan dengan menggunakan algoritma K-Means, yang merupakan sebuah metode clustering dalam data mining. Dengan penerapannya pada metode elbow untuk menentukan jumlah cluster yang optimal, dalam Penelitian ini mengelompokkan wajib pajak menjadi 3 kelompok cluster. yaitu cluster 1 (sangat patuh) terdapat 317 wajib pajak, cluster 2 (patuh) terdapat 345 wajib pajak, dan cluster 3 (tidak patuh) terdapat 338 wajib pajak. Dan hasil evaluasi DBI terkait penelitian ini menunjukkan hasil cukup memuaskan dengan nilai 0,522 dari pengelompokan 1000 data dengan 6 kali iterasi yang di lakukan.