diff --git a/tls/gnutls/gtlsconnection-gnutls.c b/tls/gnutls/gtlsconnection-gnutls.c
--- a/tls/gnutls/gtlsconnection-gnutls.c
+++ b/tls/gnutls/gtlsconnection-gnutls.c
@@ -195,18 +195,39 @@ g_tls_connection_gnutls_init_priorities 
 {
   /* First field is "ssl3 only", second is "allow unsafe rehandshaking" */
 
-  gnutls_priority_init (&priorities[FALSE][FALSE],
-			"NORMAL:%COMPAT",
-			NULL);
-  gnutls_priority_init (&priorities[TRUE][FALSE],
-			"NORMAL:%COMPAT:!VERS-TLS1.2:!VERS-TLS1.1:!VERS-TLS1.0",
-			NULL);
-  gnutls_priority_init (&priorities[FALSE][TRUE],
-			"NORMAL:%COMPAT:%UNSAFE_RENEGOTIATION",
-			NULL);
-  gnutls_priority_init (&priorities[TRUE][TRUE],
-			"NORMAL:%COMPAT:!VERS-TLS1.2:!VERS-TLS1.1:!VERS-TLS1.0:%UNSAFE_RENEGOTIATION",
-			NULL);
+  /*
+   * SECURE256 prefers 256-bit ciphers in version 2.12.x, but uses
+   * only 256-bit ciphers from version 3 and on.  NORMAL256 solves
+   * this by rearranging the ciphersuites from NORMAL to prefer the more
+   * secure ciphers, signature algorithms, and elliptic curves.
+   */
+  if (gnutls_check_version("3.0.0")) {
+    gnutls_priority_init (&priorities[FALSE][FALSE],
+			  NORMAL256 ":%COMPAT",
+			  NULL);
+    gnutls_priority_init (&priorities[TRUE][FALSE],
+			  NORMAL256 ":%COMPAT:!VERS-TLS1.2:!VERS-TLS1.1:!VERS-TLS1.0",
+			  NULL);
+    gnutls_priority_init (&priorities[FALSE][TRUE],
+			  NORMAL256 ":%COMPAT:%UNSAFE_RENEGOTIATION",
+			  NULL);
+    gnutls_priority_init (&priorities[TRUE][TRUE],
+			  NORMAL256 ":%COMPAT:!VERS-TLS1.2:!VERS-TLS1.1:!VERS-TLS1.0:%UNSAFE_RENEGOTIATION",
+			  NULL);
+  } else {
+    gnutls_priority_init (&priorities[FALSE][FALSE],
+			  "SECURE256:%COMPAT",
+			  NULL);
+    gnutls_priority_init (&priorities[TRUE][FALSE],
+			  "SECURE256:%COMPAT:!VERS-TLS1.2:!VERS-TLS1.1:!VERS-TLS1.0",
+			  NULL);
+    gnutls_priority_init (&priorities[FALSE][TRUE],
+			  "SECURE256:%COMPAT:%UNSAFE_RENEGOTIATION",
+			  NULL);
+    gnutls_priority_init (&priorities[TRUE][TRUE],
+			  "SECURE256:%COMPAT:!VERS-TLS1.2:!VERS-TLS1.1:!VERS-TLS1.0:%UNSAFE_RENEGOTIATION",
+			  NULL);
+  }
 }
 
 static void
diff --git a/tls/gnutls/gtlsconnection-gnutls.h b/tls/gnutls/gtlsconnection-gnutls.h
--- a/tls/gnutls/gtlsconnection-gnutls.h
+++ b/tls/gnutls/gtlsconnection-gnutls.h
@@ -18,6 +18,15 @@
 
 G_BEGIN_DECLS
 
+#define NORMAL256 "NORMAL"													\
+ ":!CIPHER-ALL:+AES-256-GCM:+AES-256-CBC:+CAMELLIA-256-CBC:+AES-128-GCM:+AES-128-CBC:+CAMELLIA-128-CBC:+ARCFOUR-128:+3DES-CBC"	\
+ ":!MAC-ALL:+AEAD:+SHA256:+SHA1:+MD5"												\
+ ":!CURVE-ALL:+CURVE-SECP521R1:+CURVE-SECP384R1:+CURVE-SECP256R1:+CURVE-SECP224R1:+CURVE-SECP192R1"				\
+ ":!SIGN-ALL:+SIGN-ECDSA-SHA512:+SIGN-ECDSA-SHA384:+SIGN-ECDSA-SHA256:+SIGN-ECDSA-SHA224:+SIGN-ECDSA-SHA1"			\
+ ":+SIGN-RSA-SHA512:+SIGN-RSA-SHA384:+SIGN-RSA-SHA256:+SIGN-RSA-SHA224:+SIGN-RSA-SHA1:+SIGN-DSA-SHA256"				\
+ ":+SIGN-DSA-SHA224:+SIGN-DSA-SHA1"
+
+
 #define G_TYPE_TLS_CONNECTION_GNUTLS            (g_tls_connection_gnutls_get_type ())
 #define G_TLS_CONNECTION_GNUTLS(inst)           (G_TYPE_CHECK_INSTANCE_CAST ((inst), G_TYPE_TLS_CONNECTION_GNUTLS, GTlsConnectionGnutls))
 #define G_TLS_CONNECTION_GNUTLS_CLASS(class)    (G_TYPE_CHECK_CLASS_CAST ((class), G_TYPE_TLS_CONNECTION_GNUTLS, GTlsConnectionGnutlsClass))
