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

THE ANSWER: The problem was all of the posts for such an issue were related to older kerberos and IIS issues where proxy credentials or AllowNTLM properties were helping. My case was different. What I have discovered after hours of picking worms from the ground was that somewhat IIS installation did not include Negotiate provider under IIS Windows authentication providers list. So I had to add it and move up. My WCF service started to authenticate as expected. Here is the screenshot how it should look if you are using Windows authentication with Anonymous auth OFF.

You need to right click on Windows authentication and choose providers menu item.

Hope this helps to save some time.

I have upgraded my older version of WCF to WCF 4 with below changes, hope you can also make the similar changes.

1. Web.config:

<system.serviceModel>
      <bindings>
        <basicHttpBinding>
          <binding name="Demo_BasicHttp">
            <security mode="TransportCredentialOnly">
              <transport clientCredentialType="InheritedFromHost"/>
            </security>
          </binding>
        </basicHttpBinding>
      </bindings>
      <services>
        <service name="DemoServices.CalculatorService.ServiceImplementation.CalculatorService" behaviorConfiguration="Demo_ServiceBehavior">
          <endpoint address="" binding="basicHttpBinding"
              bindingConfiguration="Demo_BasicHttp" contract="DemoServices.CalculatorService.ServiceContracts.ICalculatorServiceContract">
            <identity>
              <dns value="localhost"/>
            </identity>
          </endpoint>
          <endpoint address="mex" binding="mexHttpBinding" contract="IMetadataExchange" />
        </service>
      </services>
      <behaviors>
        <serviceBehaviors>
          <behavior name="Demo_ServiceBehavior">
            <!-- To avoid disclosing metadata information, set the values below to false before deployment -->
            <serviceMetadata httpGetEnabled="true" httpsGetEnabled="true"/>
            <!-- To receive exception details in faults for debugging purposes, set the value below to true.  Set to false before deployment to avoid disclosing exception information -->
            <serviceDebug includeExceptionDetailInFaults="false"/>
          </behavior>
        </serviceBehaviors>
      </behaviors>
      <protocolMapping>
        <add scheme="http" binding="basicHttpBinding" bindingConfiguration="Demo_BasicHttp"/>
      </protocolMapping>
      <serviceHostingEnvironment aspNetCompatibilityEnabled="true" multipleSiteBindingsEnabled="true" />
    </system.serviceModel>

2. App.config:

    <system.serviceModel>
    <bindings>
      <basicHttpBinding>
        <binding name="BasicHttpBinding_ICalculatorServiceContract" maxBufferSize="2147483647" maxBufferPoolSize="33554432" maxReceivedMessageSize="2147483647" closeTimeout="00:10:00" sendTimeout="00:10:00" receiveTimeout="00:10:00">
          <readerQuotas maxArrayLength="2147483647" maxBytesPerRead="4096" />
          <security mode="TransportCredentialOnly">
            <transport clientCredentialType="Ntlm" proxyCredentialType="None" realm="" />
          </security>
        </binding>
      </basicHttpBinding>
    </bindings>
    <client>
      <endpoint address="http://localhost:24357/CalculatorService.svc" binding="basicHttpBinding" bindingConfiguration="BasicHttpBinding_ICalculatorServiceContract" contract="ICalculatorServiceContract" name="Demo_BasicHttp" />
    </client>
  </system.serviceModel>

For me the solution was besides using "Ntlm" as credential type:

    XxxSoapClient xxxClient = new XxxSoapClient();
    ApplyCredentials(userName, password, xxxClient.ClientCredentials);

    private static void ApplyCredentials(string userName, string password, ClientCredentials clientCredentials)
    {
        clientCredentials.UserName.UserName = userName;
        clientCredentials.UserName.Password = password;
        clientCredentials.Windows.ClientCredential.UserName = userName;
        clientCredentials.Windows.ClientCredential.Password = password;
        clientCredentials.Windows.AllowNtlm = true;
        clientCredentials.Windows.AllowedImpersonationLevel = System.Security.Principal.TokenImpersonationLevel.Impersonation;
    }