Wcf – The HTTP request is unauthorized with client authentication scheme ‘Basic’. The authentication header received from the server was ‘Negotiate,NTLM’

I am trying to connect to a service using the following settings.

<bindings>
  <basicHttpBinding>
    <binding name="EngineSoap" closeTimeout="00:01:00" openTimeout="00:01:00" receiveTimeout="00:10:00" sendTimeout="00:01:00" allowCookies="false" bypassProxyOnLocal="false" hostNameComparisonMode="StrongWildcard" maxBufferSize="2147483647" maxBufferPoolSize="524288" maxReceivedMessageSize="2147483647" messageEncoding="Text" textEncoding="utf-8" transferMode="Buffered" useDefaultWebProxy="true">
      <readerQuotas maxDepth="32" maxStringContentLength="2147483647" maxArrayLength="16384" maxBytesPerRead="4096" maxNameTableCharCount="16384"/>
      <security mode="TransportCredentialOnly">
        <transport clientCredentialType="Basic" proxyCredentialType="None" realm=""/>
        <message clientCredentialType="UserName" algorithmSuite="Default"/>
      </security>
    </binding>
  </basicHttpBinding>
</bindings>
<client>
  <endpoint address="http://addressToService" binding="basicHttpBinding" bindingConfiguration="EngineSoap" contract="TRIMAPI.EngineSoap" name="EngineSoap" />
</client>

The error that I get is as follows:

The HTTP request is unauthorized with client authentication scheme 'Basic'. The authentication header received from the server was 'Negotiate,NTLM'. ---> System.Net.WebException: The remote server returned an error: (401) Unauthorized.
   at System.Net.HttpWebRequest.GetResponse()
   at System.ServiceModel.Channels.HttpChannelFactory.HttpRequestChannel.HttpChannelRequest.WaitForReply(TimeSpan timeout)
   --- End of inner exception stack trace ---

Server stack trace: 
   at System.ServiceModel.Channels.HttpChannelUtilities.ValidateAuthentication(HttpWebRequest request, HttpWebResponse response, WebException responseException, HttpChannelFactory factory)
   at System.ServiceModel.Channels.HttpChannelUtilities.ValidateRequestReplyResponse(HttpWebRequest request, HttpWebResponse response, HttpChannelFactory factory, WebException responseException, ChannelBinding channelBinding)
   at System.ServiceModel.Channels.HttpChannelFactory.HttpRequestChannel.HttpChannelRequest.WaitForReply(TimeSpan timeout)
   at System.ServiceModel.Channels.RequestChannel.Request(Message message, TimeSpan timeout)
   at System.ServiceModel.Dispatcher.RequestChannelBinder.Request(Message message, TimeSpan timeout)
   at System.ServiceModel.Channels.ServiceChannel.Call(String action, Boolean oneway, ProxyOperationRuntime operation, Object[] ins, Object[] outs, TimeSpan timeout)
   at System.ServiceModel.Channels.ServiceChannel.Call(String action, Boolean oneway, ProxyOperationRuntime operation, Object[] ins, Object[] outs)
   at System.ServiceModel.Channels.ServiceChannelProxy.InvokeService(IMethodCallMessage methodCall, ProxyOperationRuntime operation)
   at System.ServiceModel.Channels.ServiceChannelProxy.Invoke(IMessage message)

I tried to change clientCredentialType="Basic" to both "Windows" and "Ntlm" but in vain. I can't set the security mode to anything other than "TransportCredentialOnly" as the service doesn't use SSL.

Also, the username is something like 'domain\username'.

What am I missing?