Health is an investment to support economic development and has an important role in poverty eradication. However, the quality of health in some subdistricts in Sumenep Regency, East Java, Indonesia is still below the standard based on three health indicators namely nutrition and health program, infectious disease control, and environmental health and behavior. Considering these indicators, the government encounters some difficulties in choosing which indicators should be prioritized in each subdistrict to improve the quality of health and allocate the budget. Here in this study, we employed cluster analysis to map 27 subdistricts in Sumenep based on three health indicators with the k-medoids method. The k-medoids method is a partitioning method of clustering that aims to find a set of k-clusters among the data that best characterize objects in a data set. The K-Medoids are robust to the existence of outliers and perform better for large data sets. The result reveals that the k-medoid method grouped 27 subdistricts into two clusters, cluster 1 consisting of 22 subdistricts and cluster 2 consisting of 5 subdistricts. Cluster 1 represents subdistricts with a low level of nutrition and health program implementation as well as infectious disease control, but a high level of environmental health and behavior indicators implementation. Moreover, Cluster 2 indicates subdistricts with low environmental health and behavior implementation, despite the high implementation of the other two indicators. Based on the findings we recommend the government should focus on improving nutrition and infectious disease programs for subdistricts in Cluster 1 and improving environmental conditions and behavior for subdistricts in Cluster 2.