diff --git a/src/if_py_both.h b/src/if_py_both.h
index 73fa56c..99fdd80 100644
--- a/src/if_py_both.h
+++ b/src/if_py_both.h
@@ -1236,6 +1236,7 @@
     if (*key == NUL)
     {
 	RAISE_NO_EMPTY_KEYS;
+	Py_XDECREF(todecref);
 	return -1;
     }
 
@@ -1254,11 +1255,15 @@
 	hi = hash_find(&dict->dv_hashtab, di->di_key);
 	hash_remove(&dict->dv_hashtab, hi);
 	dictitem_free(di);
+	Py_XDECREF(todecref);
 	return 0;
     }
 
     if (ConvertFromPyObject(valObject, &tv) == -1)
+    {
+	Py_XDECREF(todecref);
 	return -1;
+    }
 
     if (di == NULL)
     {
@@ -2505,11 +2510,8 @@
 	PyObject	*todecref;
 
 	if ((val = StringToChars(valObject, &todecref)))
-	{
 	    r = set_option_value_for(key, 0, val, opt_flags,
 				    self->opt_type, self->from);
-	    Py_XDECREF(todecref);
-	}
 	else
 	    r = -1;
     }
diff --git a/src/testdir/test86.in b/src/testdir/test86.in
index 6929f67..a50480c 100644
--- a/src/testdir/test86.in
+++ b/src/testdir/test86.in
@@ -867,6 +867,7 @@
     return subexpr_test(expr, 'ConvertFromPyObject', (
         'None',                 # Not conversible
         '{"": 1}',              # Empty key not allowed
+        '{u"": 1}',             # Same, but with unicode object
         'FailingMapping()',     #
         'FailingMappingKey()',  #
     ))
diff --git a/src/testdir/test86.ok b/src/testdir/test86.ok
index 5ebf108..3c22bf6 100644
--- a/src/testdir/test86.ok
+++ b/src/testdir/test86.ok
@@ -503,6 +503,7 @@
 >>> Testing ConvertFromPyObject using d["a"] = {"abc" : %s}
 d["a"] = {"abc" : None}:(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 d["a"] = {"abc" : {"": 1}}:(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+d["a"] = {"abc" : {u"": 1}}:(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 d["a"] = {"abc" : FailingMapping()}:(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 d["a"] = {"abc" : FailingMappingKey()}:(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -528,6 +529,7 @@
 >>> Testing ConvertFromPyObject using d["a"] = Mapping({"abc" : %s})
 d["a"] = Mapping({"abc" : None}):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 d["a"] = Mapping({"abc" : {"": 1}}):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+d["a"] = Mapping({"abc" : {u"": 1}}):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 d["a"] = Mapping({"abc" : FailingMapping()}):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 d["a"] = Mapping({"abc" : FailingMappingKey()}):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -538,6 +540,7 @@
 >>> Testing ConvertFromPyObject using d["a"] = %s
 d["a"] = None:(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 d["a"] = {"": 1}:(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+d["a"] = {u"": 1}:(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 d["a"] = FailingMapping():(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 d["a"] = FailingMappingKey():(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -568,6 +571,7 @@
 >>> Testing ConvertFromPyObject using d.update({"abc" : %s})
 d.update({"abc" : None}):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 d.update({"abc" : {"": 1}}):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+d.update({"abc" : {u"": 1}}):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 d.update({"abc" : FailingMapping()}):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 d.update({"abc" : FailingMappingKey()}):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -593,6 +597,7 @@
 >>> Testing ConvertFromPyObject using d.update(Mapping({"abc" : %s}))
 d.update(Mapping({"abc" : None})):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 d.update(Mapping({"abc" : {"": 1}})):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+d.update(Mapping({"abc" : {u"": 1}})):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 d.update(Mapping({"abc" : FailingMapping()})):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 d.update(Mapping({"abc" : FailingMappingKey()})):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -603,6 +608,7 @@
 >>> Testing ConvertFromPyObject using d.update(%s)
 d.update(None):(<type 'exceptions.TypeError'>, TypeError("'NoneType' object is not iterable",))
 d.update({"": 1}):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+d.update({u"": 1}):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 d.update(FailingMapping()):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 d.update(FailingMappingKey()):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -633,6 +639,7 @@
 >>> Testing ConvertFromPyObject using d.update((("a", {"abc" : %s}),))
 d.update((("a", {"abc" : None}),)):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 d.update((("a", {"abc" : {"": 1}}),)):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+d.update((("a", {"abc" : {u"": 1}}),)):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 d.update((("a", {"abc" : FailingMapping()}),)):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 d.update((("a", {"abc" : FailingMappingKey()}),)):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -658,6 +665,7 @@
 >>> Testing ConvertFromPyObject using d.update((("a", Mapping({"abc" : %s})),))
 d.update((("a", Mapping({"abc" : None})),)):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 d.update((("a", Mapping({"abc" : {"": 1}})),)):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+d.update((("a", Mapping({"abc" : {u"": 1}})),)):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 d.update((("a", Mapping({"abc" : FailingMapping()})),)):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 d.update((("a", Mapping({"abc" : FailingMappingKey()})),)):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -668,6 +676,7 @@
 >>> Testing ConvertFromPyObject using d.update((("a", %s),))
 d.update((("a", None),)):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 d.update((("a", {"": 1}),)):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+d.update((("a", {u"": 1}),)):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 d.update((("a", FailingMapping()),)):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 d.update((("a", FailingMappingKey()),)):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -701,6 +710,7 @@
 >>> Testing ConvertFromPyObject using vim.List([{"abc" : %s}])
 vim.List([{"abc" : None}]):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 vim.List([{"abc" : {"": 1}}]):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+vim.List([{"abc" : {u"": 1}}]):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 vim.List([{"abc" : FailingMapping()}]):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 vim.List([{"abc" : FailingMappingKey()}]):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -726,6 +736,7 @@
 >>> Testing ConvertFromPyObject using vim.List([Mapping({"abc" : %s})])
 vim.List([Mapping({"abc" : None})]):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 vim.List([Mapping({"abc" : {"": 1}})]):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+vim.List([Mapping({"abc" : {u"": 1}})]):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 vim.List([Mapping({"abc" : FailingMapping()})]):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 vim.List([Mapping({"abc" : FailingMappingKey()})]):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -736,6 +747,7 @@
 >>> Testing ConvertFromPyObject using vim.List([%s])
 vim.List([None]):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 vim.List([{"": 1}]):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+vim.List([{u"": 1}]):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 vim.List([FailingMapping()]):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 vim.List([FailingMappingKey()]):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -768,6 +780,7 @@
 >>> Testing ConvertFromPyObject using l[:] = [{"abc" : %s}]
 l[:] = [{"abc" : None}]:(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 l[:] = [{"abc" : {"": 1}}]:(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+l[:] = [{"abc" : {u"": 1}}]:(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 l[:] = [{"abc" : FailingMapping()}]:(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 l[:] = [{"abc" : FailingMappingKey()}]:(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -793,6 +806,7 @@
 >>> Testing ConvertFromPyObject using l[:] = [Mapping({"abc" : %s})]
 l[:] = [Mapping({"abc" : None})]:(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 l[:] = [Mapping({"abc" : {"": 1}})]:(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+l[:] = [Mapping({"abc" : {u"": 1}})]:(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 l[:] = [Mapping({"abc" : FailingMapping()})]:(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 l[:] = [Mapping({"abc" : FailingMappingKey()})]:(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -803,6 +817,7 @@
 >>> Testing ConvertFromPyObject using l[:] = [%s]
 l[:] = [None]:(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 l[:] = [{"": 1}]:(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+l[:] = [{u"": 1}]:(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 l[:] = [FailingMapping()]:(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 l[:] = [FailingMappingKey()]:(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -829,6 +844,7 @@
 >>> Testing ConvertFromPyObject using l.extend([{"abc" : %s}])
 l.extend([{"abc" : None}]):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 l.extend([{"abc" : {"": 1}}]):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+l.extend([{"abc" : {u"": 1}}]):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 l.extend([{"abc" : FailingMapping()}]):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 l.extend([{"abc" : FailingMappingKey()}]):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -854,6 +870,7 @@
 >>> Testing ConvertFromPyObject using l.extend([Mapping({"abc" : %s})])
 l.extend([Mapping({"abc" : None})]):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 l.extend([Mapping({"abc" : {"": 1}})]):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+l.extend([Mapping({"abc" : {u"": 1}})]):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 l.extend([Mapping({"abc" : FailingMapping()})]):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 l.extend([Mapping({"abc" : FailingMappingKey()})]):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -864,6 +881,7 @@
 >>> Testing ConvertFromPyObject using l.extend([%s])
 l.extend([None]):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 l.extend([{"": 1}]):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+l.extend([{u"": 1}]):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 l.extend([FailingMapping()]):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 l.extend([FailingMappingKey()]):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -899,6 +917,7 @@
 >>> Testing ConvertFromPyObject using f({"abc" : %s})
 f({"abc" : None}):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 f({"abc" : {"": 1}}):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+f({"abc" : {u"": 1}}):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 f({"abc" : FailingMapping()}):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 f({"abc" : FailingMappingKey()}):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -924,6 +943,7 @@
 >>> Testing ConvertFromPyObject using f(Mapping({"abc" : %s}))
 f(Mapping({"abc" : None})):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 f(Mapping({"abc" : {"": 1}})):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+f(Mapping({"abc" : {u"": 1}})):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 f(Mapping({"abc" : FailingMapping()})):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 f(Mapping({"abc" : FailingMappingKey()})):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -934,6 +954,7 @@
 >>> Testing ConvertFromPyObject using f(%s)
 f(None):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 f({"": 1}):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+f({u"": 1}):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 f(FailingMapping()):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 f(FailingMappingKey()):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -959,6 +980,7 @@
 >>> Testing ConvertFromPyObject using fd(self={"abc" : %s})
 fd(self={"abc" : None}):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 fd(self={"abc" : {"": 1}}):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+fd(self={"abc" : {u"": 1}}):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 fd(self={"abc" : FailingMapping()}):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 fd(self={"abc" : FailingMappingKey()}):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -984,6 +1006,7 @@
 >>> Testing ConvertFromPyObject using fd(self=Mapping({"abc" : %s}))
 fd(self=Mapping({"abc" : None})):(<type 'exceptions.TypeError'>, TypeError('unable to convert to vim structure',))
 fd(self=Mapping({"abc" : {"": 1}})):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+fd(self=Mapping({"abc" : {u"": 1}})):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 fd(self=Mapping({"abc" : FailingMapping()})):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 fd(self=Mapping({"abc" : FailingMappingKey()})):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
@@ -994,6 +1017,7 @@
 >>> Testing ConvertFromPyObject using fd(self=%s)
 fd(self=None):(<type 'exceptions.TypeError'>, TypeError('unable to convert object to vim dictionary',))
 fd(self={"": 1}):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
+fd(self={u"": 1}):(<type 'exceptions.ValueError'>, ValueError('empty keys are not allowed',))
 fd(self=FailingMapping()):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 fd(self=FailingMappingKey()):(<type 'exceptions.NotImplementedError'>, NotImplementedError())
 <<< Finished
diff --git a/src/testdir/test87.in b/src/testdir/test87.in
index cf5d5e2..5ebb462 100644
--- a/src/testdir/test87.in
+++ b/src/testdir/test87.in
@@ -833,7 +833,8 @@
     iter_test(expr)
     return subexpr_test(expr, 'ConvertFromPyObject', (
         'None',                 # Not conversible
-        '{"": 1}',              # Empty key not allowed
+        '{b"": 1}',             # Empty key not allowed
+        '{"": 1}',              # Same, but with unicode object
         'FailingMapping()',     #
         'FailingMappingKey()',  #
     ))
diff --git a/src/testdir/test87.ok b/src/testdir/test87.ok
index 49ad4e4..01ff127 100644
--- a/src/testdir/test87.ok
+++ b/src/testdir/test87.ok
@@ -495,6 +495,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using d["a"] = {"abc" : %s}
 d["a"] = {"abc" : None}:(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+d["a"] = {"abc" : {b"": 1}}:(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d["a"] = {"abc" : {"": 1}}:(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d["a"] = {"abc" : FailingMapping()}:(<class 'NotImplementedError'>, NotImplementedError())
 d["a"] = {"abc" : FailingMappingKey()}:(<class 'NotImplementedError'>, NotImplementedError())
@@ -520,6 +521,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using d["a"] = Mapping({"abc" : %s})
 d["a"] = Mapping({"abc" : None}):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+d["a"] = Mapping({"abc" : {b"": 1}}):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d["a"] = Mapping({"abc" : {"": 1}}):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d["a"] = Mapping({"abc" : FailingMapping()}):(<class 'NotImplementedError'>, NotImplementedError())
 d["a"] = Mapping({"abc" : FailingMappingKey()}):(<class 'NotImplementedError'>, NotImplementedError())
@@ -530,6 +532,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using d["a"] = %s
 d["a"] = None:(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+d["a"] = {b"": 1}:(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d["a"] = {"": 1}:(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d["a"] = FailingMapping():(<class 'NotImplementedError'>, NotImplementedError())
 d["a"] = FailingMappingKey():(<class 'NotImplementedError'>, NotImplementedError())
@@ -564,6 +567,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using d.update({"abc" : %s})
 d.update({"abc" : None}):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+d.update({"abc" : {b"": 1}}):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d.update({"abc" : {"": 1}}):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d.update({"abc" : FailingMapping()}):(<class 'NotImplementedError'>, NotImplementedError())
 d.update({"abc" : FailingMappingKey()}):(<class 'NotImplementedError'>, NotImplementedError())
@@ -589,6 +593,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using d.update(Mapping({"abc" : %s}))
 d.update(Mapping({"abc" : None})):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+d.update(Mapping({"abc" : {b"": 1}})):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d.update(Mapping({"abc" : {"": 1}})):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d.update(Mapping({"abc" : FailingMapping()})):(<class 'NotImplementedError'>, NotImplementedError())
 d.update(Mapping({"abc" : FailingMappingKey()})):(<class 'NotImplementedError'>, NotImplementedError())
@@ -599,6 +604,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using d.update(%s)
 d.update(None):(<class 'TypeError'>, TypeError("'NoneType' object is not iterable",))
+d.update({b"": 1}):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d.update({"": 1}):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d.update(FailingMapping()):(<class 'NotImplementedError'>, NotImplementedError())
 d.update(FailingMappingKey()):(<class 'NotImplementedError'>, NotImplementedError())
@@ -629,6 +635,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using d.update((("a", {"abc" : %s}),))
 d.update((("a", {"abc" : None}),)):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+d.update((("a", {"abc" : {b"": 1}}),)):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d.update((("a", {"abc" : {"": 1}}),)):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d.update((("a", {"abc" : FailingMapping()}),)):(<class 'NotImplementedError'>, NotImplementedError())
 d.update((("a", {"abc" : FailingMappingKey()}),)):(<class 'NotImplementedError'>, NotImplementedError())
@@ -654,6 +661,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using d.update((("a", Mapping({"abc" : %s})),))
 d.update((("a", Mapping({"abc" : None})),)):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+d.update((("a", Mapping({"abc" : {b"": 1}})),)):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d.update((("a", Mapping({"abc" : {"": 1}})),)):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d.update((("a", Mapping({"abc" : FailingMapping()})),)):(<class 'NotImplementedError'>, NotImplementedError())
 d.update((("a", Mapping({"abc" : FailingMappingKey()})),)):(<class 'NotImplementedError'>, NotImplementedError())
@@ -664,6 +672,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using d.update((("a", %s),))
 d.update((("a", None),)):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+d.update((("a", {b"": 1}),)):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d.update((("a", {"": 1}),)):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 d.update((("a", FailingMapping()),)):(<class 'NotImplementedError'>, NotImplementedError())
 d.update((("a", FailingMappingKey()),)):(<class 'NotImplementedError'>, NotImplementedError())
@@ -701,6 +710,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using vim.List([{"abc" : %s}])
 vim.List([{"abc" : None}]):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+vim.List([{"abc" : {b"": 1}}]):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 vim.List([{"abc" : {"": 1}}]):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 vim.List([{"abc" : FailingMapping()}]):(<class 'NotImplementedError'>, NotImplementedError())
 vim.List([{"abc" : FailingMappingKey()}]):(<class 'NotImplementedError'>, NotImplementedError())
@@ -726,6 +736,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using vim.List([Mapping({"abc" : %s})])
 vim.List([Mapping({"abc" : None})]):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+vim.List([Mapping({"abc" : {b"": 1}})]):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 vim.List([Mapping({"abc" : {"": 1}})]):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 vim.List([Mapping({"abc" : FailingMapping()})]):(<class 'NotImplementedError'>, NotImplementedError())
 vim.List([Mapping({"abc" : FailingMappingKey()})]):(<class 'NotImplementedError'>, NotImplementedError())
@@ -736,6 +747,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using vim.List([%s])
 vim.List([None]):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+vim.List([{b"": 1}]):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 vim.List([{"": 1}]):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 vim.List([FailingMapping()]):(<class 'NotImplementedError'>, NotImplementedError())
 vim.List([FailingMappingKey()]):(<class 'NotImplementedError'>, NotImplementedError())
@@ -772,6 +784,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using l[:] = [{"abc" : %s}]
 l[:] = [{"abc" : None}]:(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+l[:] = [{"abc" : {b"": 1}}]:(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 l[:] = [{"abc" : {"": 1}}]:(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 l[:] = [{"abc" : FailingMapping()}]:(<class 'NotImplementedError'>, NotImplementedError())
 l[:] = [{"abc" : FailingMappingKey()}]:(<class 'NotImplementedError'>, NotImplementedError())
@@ -797,6 +810,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using l[:] = [Mapping({"abc" : %s})]
 l[:] = [Mapping({"abc" : None})]:(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+l[:] = [Mapping({"abc" : {b"": 1}})]:(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 l[:] = [Mapping({"abc" : {"": 1}})]:(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 l[:] = [Mapping({"abc" : FailingMapping()})]:(<class 'NotImplementedError'>, NotImplementedError())
 l[:] = [Mapping({"abc" : FailingMappingKey()})]:(<class 'NotImplementedError'>, NotImplementedError())
@@ -807,6 +821,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using l[:] = [%s]
 l[:] = [None]:(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+l[:] = [{b"": 1}]:(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 l[:] = [{"": 1}]:(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 l[:] = [FailingMapping()]:(<class 'NotImplementedError'>, NotImplementedError())
 l[:] = [FailingMappingKey()]:(<class 'NotImplementedError'>, NotImplementedError())
@@ -837,6 +852,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using l.extend([{"abc" : %s}])
 l.extend([{"abc" : None}]):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+l.extend([{"abc" : {b"": 1}}]):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 l.extend([{"abc" : {"": 1}}]):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 l.extend([{"abc" : FailingMapping()}]):(<class 'NotImplementedError'>, NotImplementedError())
 l.extend([{"abc" : FailingMappingKey()}]):(<class 'NotImplementedError'>, NotImplementedError())
@@ -862,6 +878,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using l.extend([Mapping({"abc" : %s})])
 l.extend([Mapping({"abc" : None})]):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+l.extend([Mapping({"abc" : {b"": 1}})]):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 l.extend([Mapping({"abc" : {"": 1}})]):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 l.extend([Mapping({"abc" : FailingMapping()})]):(<class 'NotImplementedError'>, NotImplementedError())
 l.extend([Mapping({"abc" : FailingMappingKey()})]):(<class 'NotImplementedError'>, NotImplementedError())
@@ -872,6 +889,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using l.extend([%s])
 l.extend([None]):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+l.extend([{b"": 1}]):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 l.extend([{"": 1}]):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 l.extend([FailingMapping()]):(<class 'NotImplementedError'>, NotImplementedError())
 l.extend([FailingMappingKey()]):(<class 'NotImplementedError'>, NotImplementedError())
@@ -907,6 +925,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using f({"abc" : %s})
 f({"abc" : None}):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+f({"abc" : {b"": 1}}):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 f({"abc" : {"": 1}}):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 f({"abc" : FailingMapping()}):(<class 'NotImplementedError'>, NotImplementedError())
 f({"abc" : FailingMappingKey()}):(<class 'NotImplementedError'>, NotImplementedError())
@@ -932,6 +951,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using f(Mapping({"abc" : %s}))
 f(Mapping({"abc" : None})):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+f(Mapping({"abc" : {b"": 1}})):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 f(Mapping({"abc" : {"": 1}})):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 f(Mapping({"abc" : FailingMapping()})):(<class 'NotImplementedError'>, NotImplementedError())
 f(Mapping({"abc" : FailingMappingKey()})):(<class 'NotImplementedError'>, NotImplementedError())
@@ -942,6 +962,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using f(%s)
 f(None):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+f({b"": 1}):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 f({"": 1}):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 f(FailingMapping()):(<class 'NotImplementedError'>, NotImplementedError())
 f(FailingMappingKey()):(<class 'NotImplementedError'>, NotImplementedError())
@@ -967,6 +988,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using fd(self={"abc" : %s})
 fd(self={"abc" : None}):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+fd(self={"abc" : {b"": 1}}):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 fd(self={"abc" : {"": 1}}):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 fd(self={"abc" : FailingMapping()}):(<class 'NotImplementedError'>, NotImplementedError())
 fd(self={"abc" : FailingMappingKey()}):(<class 'NotImplementedError'>, NotImplementedError())
@@ -992,6 +1014,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using fd(self=Mapping({"abc" : %s}))
 fd(self=Mapping({"abc" : None})):(<class 'TypeError'>, TypeError('unable to convert to vim structure',))
+fd(self=Mapping({"abc" : {b"": 1}})):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 fd(self=Mapping({"abc" : {"": 1}})):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 fd(self=Mapping({"abc" : FailingMapping()})):(<class 'NotImplementedError'>, NotImplementedError())
 fd(self=Mapping({"abc" : FailingMappingKey()})):(<class 'NotImplementedError'>, NotImplementedError())
@@ -1002,6 +1025,7 @@
 <<< Finished
 >>> Testing ConvertFromPyObject using fd(self=%s)
 fd(self=None):(<class 'TypeError'>, TypeError('unable to convert object to vim dictionary',))
+fd(self={b"": 1}):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 fd(self={"": 1}):(<class 'ValueError'>, ValueError('empty keys are not allowed',))
 fd(self=FailingMapping()):(<class 'NotImplementedError'>, NotImplementedError())
 fd(self=FailingMappingKey()):(<class 'NotImplementedError'>, NotImplementedError())
diff --git a/src/version.c b/src/version.c
index 9b13b2d..2e61a80 100644
--- a/src/version.c
+++ b/src/version.c
@@ -729,6 +729,8 @@
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    1100,
+/**/
     1099,
 /**/
     1098,