diff --git a/src/server/e-ews-connection-utils.c b/src/server/e-ews-connection-utils.c
index 9fb06cc..30be960 100644
--- a/src/server/e-ews-connection-utils.c
+++ b/src/server/e-ews-connection-utils.c
@@ -22,6 +22,9 @@
 
 #include <string.h>
 
+#include <glib.h>
+#include <glib/gstdio.h>
+
 #include "e-ews-connection-utils.h"
 
 #define EWS_GSSAPI_SOUP_SESSION "ews-gssapi-soup-session"
@@ -109,6 +112,81 @@ e_ews_connection_utils_check_element (const gchar *function_name,
 	return TRUE;
 }
 
+static gboolean
+ews_connect_check_ntlm_available (CamelNetworkSettings *network_settings)
+{
+#ifndef G_OS_WIN32
+	#define NTLM_AUTH_HELPER "/usr/bin/ntlm_auth"
+
+	CamelStream *stream;
+	const gchar *cp;
+	gchar *user;
+	gchar buf[1024];
+	gsize s;
+	gchar *command;
+	gint ret;
+
+	g_return_val_if_fail (CAMEL_IS_NETWORK_SETTINGS (network_settings), FALSE);
+
+	if (g_access (NTLM_AUTH_HELPER, X_OK))
+		return FALSE;
+
+	user = camel_network_settings_dup_user (network_settings);
+
+	g_return_val_if_fail (user != NULL, FALSE);
+
+	cp = strchr (user, '\\');
+	if (cp != NULL) {
+		command = g_strdup_printf (
+			"%s --helper-protocol ntlmssp-client-1 "
+			"--use-cached-creds --username '%s' "
+			"--domain '%.*s'", NTLM_AUTH_HELPER,
+			cp + 1, (gint)(cp - user), user);
+	} else {
+		command = g_strdup_printf (
+			"%s --helper-protocol ntlmssp-client-1 "
+			"--use-cached-creds --username '%s'",
+			NTLM_AUTH_HELPER, user);
+	}
+
+	stream = camel_stream_process_new ();
+
+	ret = camel_stream_process_connect (CAMEL_STREAM_PROCESS (stream), command, NULL, NULL);
+
+	g_free (command);
+	g_free (user);
+
+	if (ret) {
+		g_object_unref (stream);
+		return FALSE;
+	}
+
+	if (camel_stream_write_string (stream, "YR\n", NULL, NULL) < 0) {
+		g_object_unref (stream);
+		return FALSE;
+	}
+
+	s = camel_stream_read (stream, buf, sizeof (buf), NULL, NULL);
+	if (s < 4) {
+		g_object_unref (stream);
+		return FALSE;
+	}
+
+	if (buf[0] != 'Y' || buf[1] != 'R' || buf[2] != ' ' || buf[s - 1] != '\n') {
+		g_object_unref (stream);
+		return FALSE;
+	}
+
+	g_object_unref (stream);
+
+	return TRUE;
+#else
+	g_return_val_if_fail (CAMEL_IS_NETWORK_SETTINGS (network_settings), FALSE);
+
+	/* Win32 should be able to use SSPI here. */
+	return FALSE;
+#endif
+}
 /* Return TRUE if using GSSAPI.  */
 gboolean
 e_ews_connection_utils_get_without_password (CamelEwsSettings *ews_settings)
@@ -119,6 +197,9 @@ e_ews_connection_utils_get_without_password (CamelEwsSettings *ews_settings)
 	g_object_get (G_OBJECT (ews_settings), "auth-mechanism", &auth_mech, NULL);
 	if (g_strcmp0 (auth_mech, "GSSAPI") == 0)
 		result = TRUE;
+	else if (g_strcmp0 (auth_mech, "PLAIN") != 0)
+		result = ews_connect_check_ntlm_available (
+			CAMEL_NETWORK_SETTINGS (ews_settings));
 
 	g_free (auth_mech);
 
diff --git a/src/server/e-ews-connection.c b/src/server/e-ews-connection.c
index 0a5a20f..7306fed 100644
--- a/src/server/e-ews-connection.c
+++ b/src/server/e-ews-connection.c
@@ -1921,6 +1921,7 @@ ews_connection_authenticate (SoupSession *sess,
 {
 	EEwsConnection *cnc = data;
 	CamelNetworkSettings *network_settings;
+	const char *scheme = soup_auth_get_scheme_name (auth);
 	gchar *user, *password;
 
 	g_return_if_fail (cnc != NULL);
@@ -1933,9 +1934,27 @@ ews_connection_authenticate (SoupSession *sess,
 
 	password = e_ews_connection_dup_password (cnc);
 
-	if (password != NULL)
-		soup_auth_authenticate (auth, user, password);
+	if (password && !password[0] &&
+	    g_ascii_strcasecmp(scheme, "Negotiate")) {
+		/* We only want to call soup_auth_authenticate() with an
+		 * empty password for Negotiate auth. For Basic and NTLM
+		 * that means there's no password, so just let it fail. */
+		password = NULL;
+	}
 
+	if (password)
+		soup_auth_authenticate (auth, user, password);
+	else {
+		/* The NTLM implementation in libsoup doesn't cope very well
+		 * with recovering from authentication failures (bug 703181).
+		 * So cancel the message now while it's in-flight, and we'll
+		 * get a shiny new connection for the next attempt. */
+		if (!g_ascii_strcasecmp(scheme, "NTLM")) {
+			soup_session_cancel_message(cnc->priv->soup_session,
+						    msg,
+						    SOUP_STATUS_UNAUTHORIZED);
+		}
+	}
 	g_free (password);
 	g_free (user);
 }
