This is pretty similar to my question: "What should we implement to authorize clients to use our web service?"
We ended up not publishing the WSDL and only serving up the service via https and requiring basic authentication. DON'T use basic auth if you can't force all clients to use https.
If this is a .net web service then here is the config file entry to keep the wsdl from being published.
<system.web>
<webServices>
<protocols>
<remove name="Documentation" />
</protocols>
</webServices>
</system.web>
When you goto the page, you'll receive an error message similar to the message you'd get if you tried to manually pull down a web.config from a site. As Steven points out, this is security through obscurity and should NOT be used by itself to secure your web service. However, when used in addition to basic auth + https, its a nice little extra.
Client Side Code:
To access this web service from a client, add your web reference the normal way and in the calling code (assuming your web reference is named WebRef).
WebRef.Url = "url";
WebRef.Credentials = new System.Net.NetworkCredential("userid", "password");
Also, you may want to look into WebRef.PreAuthenticate to save some round trips. Just be warned that you'll have a fun time testing that out if you're behind a corporate proxy. Proxies are used via the WebRef by
WebRef.Proxy = new WebProxy("url");
WebRef.Proxy.Credentials = new System.Net.NetworkCredential("userid", "password");