static void CreateContact()
{
    // Create the bindings and set the credentials.
    ExchangeServiceBinding esb = new ExchangeServiceBinding();
    esb.Url = "http://fqdn/ews/exchange.asmx";

    esb.Credentials = new NetworkCredential("UserName", "Password", "Domain");

    // Create an object of create item type.
    CreateItemType createItemType = new CreateItemType();

    // Because you are creating a contact, save the item in the Contacts folder.
    createItemType.SavedItemFolderId = new TargetFolderIdType();
    DistinguishedFolderIdType contactsFolder = new DistinguishedFolderIdType();
    contactsFolder.Id = DistinguishedFolderIdNameType.contacts;

    createItemType.SavedItemFolderId.Item = contactsFolder;

    createItemType.Items = new NonEmptyArrayOfAllItemsType();
    createItemType.Items.Items = new ItemType[1];

    // Create a contact item type.
    ContactItemType contactItem = new ContactItemType();

    // Set the relevant properties on the contact.
    contactItem.FileAs = "Friend A";

    // Set the contact name and job information.
    contactItem.GivenName = "Don";
    contactItem.Surname = "Hall";
    contactItem.CompanyName = "AdventureWorks";
    contactItem.JobTitle = "Software Engineer";

    // Set a single e-mail address for the contact.
    contactItem.EmailAddresses = new EmailAddressDictionaryEntryType[1];
    EmailAddressDictionaryEntryType address = new EmailAddressDictionaryEntryType();
    address.Key = EmailAddressKeyType.EmailAddress1;
    address.Value = "don@example.com";
    contactItem.EmailAddresses[0] = address;

    // Set a single contact physical address.
    contactItem.PhysicalAddresses = new PhysicalAddressDictionaryEntryType[1];
    PhysicalAddressDictionaryEntryType physicalAddress = new PhysicalAddressDictionaryEntryType();
    physicalAddress.Key = PhysicalAddressKeyType.Home;
    physicalAddress.Street = "1234 56 Ave NE";
    physicalAddress.City = "La Habra Heights";
    physicalAddress.Country = "United States";
    physicalAddress.PostalCode = "98072";

    contactItem.PhysicalAddresses[0] = physicalAddress;

    // Set the contact telephone number.
    contactItem.PhoneNumbers = new PhoneNumberDictionaryEntryType[1];
    PhoneNumberDictionaryEntryType phoneEntry = new PhoneNumberDictionaryEntryType();
    phoneEntry.Key = PhoneNumberKeyType.BusinessPhone;
    phoneEntry.Value = "5625550100";

    contactItem.PhoneNumbers[0] = phoneEntry;

    createItemType.Items.Items[0] = contactItem;

    // Send the request to create the contact item; receive the response.
    CreateItemResponseType createItemResponse = esb.CreateItem(createItemType);

    // Check the results of the request.
    if (createItemResponse.ResponseMessages.Items.Length > 0 &&
        createItemResponse.ResponseMessages.Items[0].ResponseClass == ResponseClassType.Success)
    {
        ItemInfoResponseMessageType responseMessage = createItemResponse.ResponseMessages.Items[0] as ItemInfoResponseMessageType;
        ContactItemType contactResponse = responseMessage.Items.Items[0] as ContactItemType;
        Console.WriteLine("Created Contact Item with Id {0} and ChangeKey {1}", contactResponse.ItemId.Id, contactResponse.ItemId.ChangeKey);
    }
}

<?xml version="1.0" encoding="utf-8"?>
<CreateItem xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
            xmlns:xsd="http://www.w3.org/2001/XMLSchema">
  <SavedItemFolderId xmlns="http://schemas.microsoft.com/exchange/services/2006/messages">
    <DistinguishedFolderId Id="contacts" xmlns="http://schemas.microsoft.com/exchange/services/2006/types" />
  </SavedItemFolderId>
  <Items xmlns="http://schemas.microsoft.com/exchange/services/2006/messages">
    <Contact xmlns="http://schemas.microsoft.com/exchange/services/2006/types">
      <FileAs>Friend A</FileAs>
      <GivenName>Don</GivenName>
      <CompanyName>AdventureWorks</CompanyName>
      <EmailAddresses>
        <Entry Key="EmailAddress1">don@example.com</Entry>
      </EmailAddresses>
      <PhysicalAddresses>
        <Entry Key="Home">
          <Street>1234 56 Ave NE</Street>
          <City>La Habra Heights</City>
          <Country>United States</Country>
          <PostalCode>98072</PostalCode>
        </Entry>
      </PhysicalAddresses>
      <PhoneNumbers>
        <Entry Key="BusinessPhone">5625550100</Entry>
      </PhoneNumbers>
      <JobTitle>Software Engineer</JobTitle>
      <Surname>Hall</Surname>
    </Contact>
  </Items>
</CreateItem>

<?xml version="1.0" encoding="utf-8"?>
<CreateItemResponse xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
                    xmlns:xsd="http://www.w3.org/2001/XMLSchema">
  <ResponseMessages xmlns="http://schemas.microsoft.com/exchange/services/2006/messages">
    <CreateItemResponseMessage ResponseClass="Success">
      <ResponseCode>NoError</ResponseCode>
      <Items>
        <Contact xmlns="http://schemas.microsoft.com/exchange/services/2006/types">
          <ItemId Id="AAAtA=" ChangeKey="EQAAABYA" />
        </Contact>
      </Items>
    </CreateItemResponseMessage>
  </ResponseMessages>
</CreateItemResponse>