diff --git a/python/proton/_message.py b/python/proton/_message.py
index 6563935..ed791c9 100644
--- a/python/proton/_message.py
+++ b/python/proton/_message.py
@@ -34,7 +34,7 @@
 
 from . import _compat
 from ._common import isinteger, millis2secs, secs2millis, unicode2utf8, utf82unicode
-from ._data import Data, symbol, ulong, AnnotationDict
+from ._data import char, Data, decimal128, symbol, ulong, AnnotationDict
 from ._endpoints import Link
 from ._exceptions import EXCEPTIONS, MessageException
 
@@ -89,16 +89,41 @@
             return err
 
     def _check_property_keys(self):
+        '''
+        AMQP allows only string keys for properties. This function checks that this requirement is met
+        and raises a MessageException if not. However, in certain cases, conversions to string are
+        automatically performed:
+
+        1. When a key is a user-defined (non-AMQP) subclass of unicode/str (py2/py3).
+           AMQP types symbol and char, although derived from unicode/str, are not converted,
+           and result in an exception.
+
+        2. In Py2, when a key is binary. This is a convenience for Py2 users that encode
+           string literals without using the u'' prefix. In Py3, this is not the case, and
+           using a binary key will result in an error. AMQP type decimal128, which is derived
+           from binary, will not be converted, and will result in an exception.
+        '''
+        # We cannot make changes to the dict while iterating, so we
+        # must save and make the changes afterwards
+        changed_keys = []
         for k in self.properties.keys():
             if isinstance(k, unicode):
-                # py2 unicode, py3 str (via hack definition)
-                continue
-            # If key is binary then change to string
-            elif isinstance(k, str):
-                # py2 str
-                self.properties[k.encode('utf-8')] = self.properties.pop(k)
+                # Py2 & Py3 strings and their subclasses
+                if type(k) is symbol or type(k) is char:
+                    # Exclude symbol and char
+                    raise MessageException('Application property key is not string type: key=%s %s' % (str(k), type(k)))
+                if type(k) is not unicode:
+                    # Only for string subclasses, convert to string
+                    changed_keys.append((k, unicode(k)))
+            elif isinstance(k, str) and not (type(k) is decimal128):
+                # Py2 only: If key is binary string then convert to unicode. Exclude bytes subclass decimal128.
+                changed_keys.append((k, k.decode('utf-8')))
             else:
+                # Anything else: raise exception
                 raise MessageException('Application property key is not string type: key=%s %s' % (str(k), type(k)))
+        # Make the key changes
+        for old_key, new_key in changed_keys:
+            self.properties[new_key] = self.properties.pop(old_key)
 
     def _pre_encode(self):
         inst = Data(pn_message_instructions(self._msg))
@@ -427,7 +452,7 @@
         The group-id for any replies.
 
         :type: ``str``
-        :raise: :exc:`MessageException` if there is any Proton error when using the setter.        
+        :raise: :exc:`MessageException` if there is any Proton error when using the setter.
         """)
 
     def _get_instructions(self):
diff --git a/python/tests/proton_tests/message.py b/python/tests/proton_tests/message.py
index 04413ee..6f407ca 100644
--- a/python/tests/proton_tests/message.py
+++ b/python/tests/proton_tests/message.py
@@ -20,6 +20,8 @@
 from __future__ import absolute_import
 
 from uuid import uuid4
+from sys import version_info
+from unittest import skipIf
 
 from proton import *
 
@@ -107,6 +109,15 @@
   def testReplyToGroupId(self):
     self._test_str("reply_to_group_id")
 
+try:
+    long()
+except NameError:
+    long = int
+try:
+    unicode()
+except NameError:
+    unicode = str
+
 class CodecTest(Test):
 
   def testProperties(self):
@@ -119,6 +130,73 @@
 
     assert msg2.properties['key'] == 'value', msg2.properties['key']
 
+  class MyStringSubclass(unicode):
+    def __repr__(self):
+      return 'MyStringSubclass(%s)' % unicode.__repr__(self)
+
+  def testStringSubclassPropertyKey(self):
+    self.msg.properties = {'abc': 123, CodecTest.MyStringSubclass('def'): 456}
+    data = self.msg.encode()
+
+    msg2 = Message()
+    msg2.decode(data)
+
+    assert msg2.properties == self.msg.properties
+    for k in msg2.properties:
+        assert type(k) is unicode, 'non-string key %s %s' % (k, type(k))
+
+  def _testNonStringPropertyKey(self, k):
+    self.msg.properties = {k: 'abc'}
+    try:
+        self.msg.encode()
+    except MessageException:
+        return
+    self.fail('Non-string property key: %s, key type: %s' % (self.msg, type(k)))
+
+  def testNonSequencePropertyKeys(self):
+    # AMQP non-string types
+    self._testNonStringPropertyKey(None)
+    self._testNonStringPropertyKey(True)
+    self._testNonStringPropertyKey(byte(1))
+    self._testNonStringPropertyKey(ubyte(2))
+    self._testNonStringPropertyKey(short(3))
+    self._testNonStringPropertyKey(ushort(4))
+    self._testNonStringPropertyKey(int32(5))
+    self._testNonStringPropertyKey(uint(6))
+    self._testNonStringPropertyKey(long(7))
+    self._testNonStringPropertyKey(ulong(8))
+    self._testNonStringPropertyKey(float32(9.0))
+    self._testNonStringPropertyKey(10.0)
+    self._testNonStringPropertyKey(decimal32(11))
+    self._testNonStringPropertyKey(decimal64(12))
+    self._testNonStringPropertyKey(timestamp(1234567890))
+    self._testNonStringPropertyKey(uuid4())
+
+  def testCharPropertyKey(self):
+    self._testNonStringPropertyKey(char('A'))
+
+  def testDecimal128PropertyKey(self):
+    self._testNonStringPropertyKey(decimal128(b'12345'))
+
+  def testSymbolPropertyKey(self):
+    self._testNonStringPropertyKey(symbol('abcdef'))
+
+  def testBinaryPropertyKey(self):
+    if version_info[0] > 2:
+      # Py3: Binary conversions not supported
+      self._testNonStringPropertyKey(b'abc123')
+    else:
+      # Py2: Check for correct key conversion
+      self.msg.properties = {'abc': 123, b'def': 456}
+      data = self.msg.encode()
+
+      msg2 = Message()
+      msg2.decode(data)
+
+      assert msg2.properties == self.msg.properties
+      for k in msg2.properties:
+        assert type(k) is unicode, 'non-string key %s %s' % (k, type(k))
+
   def testAnnotationsSymbolicAndUlongKey(self, a={symbol('one'): 1, 'two': 2, ulong(3): 'three'}):
     self.msg.annotations = a
     data = self.msg.encode()