How can I pass a username/password in the header to a SOAP WCF Service

The answers above are so wrong! DO NOT add custom headers. Judging from your sample xml, it is a standard WS-Security header. WCF definitely supports it out of the box. When you add a service reference you should have basicHttpBinding binding created for you in the config file. You will have to modify it to include security element with mode TransportWithMessageCredential and message element with clientCredentialType = UserName:

<basicHttpBinding>
  <binding name="usernameHttps">
    <security mode="TransportWithMessageCredential">
      <message clientCredentialType="UserName"/>
    </security>
  </binding>
</basicHttpBinding>

The config above is telling WCF to expect userid/password in the SOAP header over HTTPS. Then you can set id/password in your code before making a call:

var service = new MyServiceClient();
service.ClientCredentials.UserName.UserName = "username";
service.ClientCredentials.UserName.Password = "password";

Unless this particular service provider deviated from the standard, it should work.

There is probably a smarter way, but you can add the headers manually like this:

var client = new IdentityProofingService.IdentityProofingWSClient();

using (new OperationContextScope(client.InnerChannel))
{
    OperationContext.Current.OutgoingMessageHeaders.Add(
        new SecurityHeader("UsernameToken-49", "12345/userID", "password123"));
    client.invokeIdentityService(new IdentityProofingRequest());
}

Here, SecurityHeader is a custom implemented class, which needs a few other classes since I chose to use attributes to configure the XML serialization:

public class SecurityHeader : MessageHeader
{
    private readonly UsernameToken _usernameToken;

    public SecurityHeader(string id, string username, string password)
    {
        _usernameToken = new UsernameToken(id, username, password);
    }

    public override string Name
    {
        get { return "Security"; }
    }

    public override string Namespace
    {
        get { return "http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd"; }
    }

    protected override void OnWriteHeaderContents(XmlDictionaryWriter writer, MessageVersion messageVersion)
    {
        XmlSerializer serializer = new XmlSerializer(typeof(UsernameToken));
        serializer.Serialize(writer, _usernameToken);
    }
}


[XmlRoot(Namespace = "http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd")]
public class UsernameToken
{
    public UsernameToken()
    {
    }

    public UsernameToken(string id, string username, string password)
    {
        Id = id;
        Username = username;
        Password = new Password() {Value = password};
    }

    [XmlAttribute(Namespace = "http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd")]
    public string Id { get; set; }

    [XmlElement]
    public string Username { get; set; }

    [XmlElement]
    public Password Password { get; set; }
}

public class Password
{
    public Password()
    {
        Type = "http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-username-token-profile-1.0#PasswordText";
    }

    [XmlAttribute]
    public string Type { get; set; }

    [XmlText]
    public string Value { get; set; }
}

I have not added the Nonce bit to the UsernameToken XML, but it is very similar to the Password one. The Created element also needs to be added still, but it's a simple [XmlElement].