Agglomerative hierarchical clustering methods is cluster analysis method whose primary purpose is to group objects based on its characteristics, it begins with the individual objects until the objects are fused into a single cluster. Agglomerative hierarchical clustering methods are divided into single linkage, complete linkage, average linkage, and ward. This research compared the four agglomerative hierarchical clustering methods in order to get the best cluster solution in the case of the classification of regencies/cities in East Java province based on the quality of “Keluarga Berencana” (KB) services. The results of this research showed that based on calculation of cophenetic correlation coefficient, the best cluster solution is produced by average linkage method. This method obtained four clusters with the different characteristics. Cluster 1 has an “extremely bad condition” on the qualification of KB clinics and the competence of KB service personnel. Cluster 2 has a “good condition” on the qualification of KB clinics and “bad condition” on the competence of KB service personnel. Cluster 3 has a “bad condition” on the qualification of KB clinics and “medium condition” on the competence of KB service personnel. Cluster 4 have a “medium condition” on the qualification of KB clinics and a “good condition” on the competence of KB service personnel