Meeting out similarity demands of clients, selection of threshold and computation of inter-cluster distance (ICD) are difficult while clustering. Hierarchical agglomerative clustering based approach is proposed for service discovery including two similarity models viz., Output Similarity Model (OSM) and Total Similarity Model (TSM) with additional levels for Degree of Match (DoM). The OSM which computes similarity between services using solely the outputs of services is proposed while clustering services to eliminate irrelevancy completely. The TSM which computes similarity between services using both inputs and outputs of services is proposed while discovering matched services of a given query. The work justifies the `complete linkage' as suitable method for computing ICD. It selects threshold-ICD in terms of DoM without altering the similarity demands of clients and ensures rightness of clusters. The computation time of discovery using clusters is found to be faster (7.32 against 170.59 seconds) than that of sequential method.