WSDL provides the potential for Web Services to enrich consumers? lives. However, it has had only limited success in enterprise environments and even less in the mass market. Apart from the difficulties and high costs involved in current approaches, another reason is the low precision for Web Services discovery using the most widely known tool: search engines. Seeking for effective ways to change the situation, we conducted an experiment to examine better approaches of using general-purpose search engines to discover Web Services. We used nine different approaches for publishing Web Services and two groups of total 18 queries for retrieving them using Yahoo and Google search engines. The queries were fired to each search engine daily over a week and the top 100 search results returned from every search are collected and analyzed. The results show that for both search engines, embedding a WSDL specification in a Web page that provides semantic description of the service yield the best results.