The Web services are distributed across the Internet, but the existing Web service discovery is processed in a centralized approach such as UDDI, which has the limitations of single point failure and performance bottleneck. We propose PWSD, a scalable Web service discovery architecture based on peer-to-peer overlay network to overcome these limitations. In PWSD, the service descriptions are managed in a completely decentralized way. Moreover, since the basic peer-to-peer routing algorithm cannot be applied directly in the service discovery process, we extend the basic peer-to-peer routing algorithm with XML, which enables PWSD to support XML-based complicate query. Experimental results show that PWSD has good robustness and scalability.