The HTTP request is unauthorized with client authentication scheme 'Anonymous'. The authentication header received from the server was 'Negotiate,NTLM

I've deployed a WCF service to IIS with security mode set to "Message":

When I tried to called it from my client app I got the following error:

The HTTP request is unauthorized with client authentication scheme 'Anonymous'. The authentication header received from the server was 'Negotiate,NTLM'.

I googled out that this is caused by security settings of the service virtual directory. I configured it to use Integrated Windows Authentication rather than allowing Anonymous access. I did so because I wanted to restrict the access to my service.

Solution:
It came out that using Anonymous Access in this particular case (WCF service in Message security mode) doesn't mean that anyone is allowed to use the service. The authentication is performed by WCF rather than IIS, but it still takes place.

Answer found here.