Found another approach here:
SoapServiceClient client = new SoapServiceClient();
using(new OperationContextScope(client.InnerChannel))
{
HttpRequestMessageProperty requestMessage = new HttpRequestMessageProperty();
requestMessage.Headers["MyHttpHeader"] = "MyHttpHeaderValue";
OperationContext.Current.OutgoingMessageProperties[HttpRequestMessageProperty.Name] = requestMessage;
var result = client.MyClientMethod();
}