Penelitian ini bertujuan untuk mengenal pelanggan sebaik mungkin mengetahui apa yang diinginkannya dan sejauh mana pelayanan yang telah diberikan sehingga muncul strategi perusahaan dalam peningkatan kualitas pelayanan yang mengarah pada reformasi bisnis di bidang industri jasa. Metode pendekatan yang digunakan adalah Dimensions of Service Quality (Zeithami, 1990). Pengambilan data dilakukan di dua kantor pelayanan yaitu Medan dan Pematang Siantar. Pengolahan data yang dilakukan adalah pembentukan segmen pelanggan berdasarkan besar tagihan (billing) dengan menggunakan metode K-Mean Cluster, pendefinisian profit pelanggan dengan menggunakan metode Crosstab, perhitungan tingkat harapan, persepsi layanan dan persepsi kualitas pelayanan dengan menggunakan Statistik Deskriptif, penentuan variabel-variabel yang diperbaiki dengan Customer. Windows. Hasil yang diperoleh dalam penelitian ini adalah rekomendasi strategi reformasi bisnis yang mengarah pada prioritas peningkatan perbaikan variabel-variabel kualitas pelayanan yaitu surat kabar, beli kartu Hallo langsung kring, tepat jumlah tagihan, tepat waktu kirim tagihan, mudah menghubungi perusahaan, kejelasan kejernihan suara, brosur/majalah, mudah dapat info tagihan, bebas gangguan saat bicara dan menu fasilitas dalam handphone Medan sedangkan untuk P. Siantar, yang harus dibenahi adalah musik kantor, surat kabar, kejelasan kejernihan suara, luas ruangan, salam ketika bertemu dengan pelanggan, penataan ruangan, sebut nama pelanggan saat kontak, mudah menghubungi perusahaan, garansi kartu Halo, tepat waktu kirim tagihan, beli kartu Hallo langsung kring dan pilihan kalimat blocking.