How to dynamically select, bind and invoke Web service that can best meet the requirements of service consumer is an ongoing research topic in Web services community. In this paper, a QoS-Guaranteed and distributed mechanism of Web service discovery is proposed, which supports Web service discovery with QoS constraints and enhances the QoS of service discovery system. First, a novel three-dimensional QoS model of Web service is introduced, and a Web service-selecting algorithm is proposed based on the novel model. Second, the implementation model of UDDI (universal description, discovery, and integration) specification is improved by integrating the service-selecting algorithm based on QoS constraints. Third, an unstructured peer-to-peer network of UDDI with an informed routing protocol based on Bloom Filters is proposed, and an extended Kautz graph is used as the logical topology of this network. The experimental results show that the new mechanism for Web service discovery possesses higher recall rate, query response rate, and better load balance. Furthermore, the results for QoS of the selected Web service can satisfy the requirements of service consumers.