diff --git a/Lib/os.py b/Lib/os.py
index 580b983..7672d6f 100644
--- a/Lib/os.py
+++ b/Lib/os.py
@@ -450,6 +450,8 @@
 def getenv(key, default=None):
     """Get an environment variable, return None if it doesn't exist.
     The optional second argument can specify an alternate default."""
+    if isinstance(key, bytes):
+        key = key.decode(sys.getfilesystemencoding(), "surrogateescape")
     return environ.get(key, default)
 __all__.append("getenv")
 
diff --git a/Lib/subprocess.py b/Lib/subprocess.py
index b8bcd5e..ff615d3 100644
--- a/Lib/subprocess.py
+++ b/Lib/subprocess.py
@@ -1090,7 +1090,10 @@
                         fs_encoding = sys.getfilesystemencoding()
                         def fs_encode(s):
                             """Encode s for use in the env, fs or cmdline."""
-                            return s.encode(fs_encoding, 'surrogateescape')
+                            if isinstance(s, bytes):
+                                return s
+                            else:
+                                return s.encode(fs_encoding, 'surrogateescape')
 
                         # We must avoid complex work that could involve
                         # malloc or free in the child process to avoid
diff --git a/Lib/test/test_subprocess.py b/Lib/test/test_subprocess.py
index d47e01c..ce53932 100644
--- a/Lib/test/test_subprocess.py
+++ b/Lib/test/test_subprocess.py
@@ -782,7 +782,7 @@
         self.assertStderrEqual(stderr, b'')
         self.assertEqual(p.wait(), -signal.SIGTERM)
 
-    def test_surrogates(self):
+    def test_surrogates_error_message(self):
         def prepare():
             raise ValueError("surrogate:\uDCff")
 
@@ -801,6 +801,28 @@
         else:
             self.fail("Expected ValueError or RuntimeError")
 
+    def test_undecodable_env(self):
+        for key, value in (('test', 'abc\uDCFF'), ('test\uDCFF', '42')):
+            value_repr = repr(value).encode("ascii")
+
+            # test str with surrogates
+            script = "import os; print(repr(os.getenv(%s)))" % repr(key)
+            stdout = subprocess.check_output(
+                [sys.executable, "-c", script],
+                env={key: value})
+            stdout = stdout.rstrip(b'\n\r')
+            self.assertEquals(stdout, value_repr)
+
+            # test bytes
+            key = key.encode("ascii", "surrogateescape")
+            value = value.encode("ascii", "surrogateescape")
+            script = "import os; print(repr(os.getenv(%s)))" % repr(key)
+            stdout = subprocess.check_output(
+                [sys.executable, "-c", script],
+                env={key: value})
+            stdout = stdout.rstrip(b'\n\r')
+            self.assertEquals(stdout, value_repr)
+
 
 @unittest.skipUnless(mswindows, "Windows specific tests")
 class Win32ProcessTestCase(BaseTestCase):
diff --git a/Misc/NEWS b/Misc/NEWS
index 128f305..555d5e8 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -333,6 +333,9 @@
 Library
 -------
 
+- Issue #8391: os.execvpe() and os.getenv() supports unicode with surrogates
+  and bytes strings for environment keys and values
+
 - Issue #8467: Pure Python implementation of subprocess encodes the error
   message using surrogatepass error handler to support surrogates in the
   message
diff --git a/Modules/posixmodule.c b/Modules/posixmodule.c
index 533f5bb..8835b0c 100644
--- a/Modules/posixmodule.c
+++ b/Modules/posixmodule.c
@@ -3052,6 +3052,86 @@
 	return posix_error();
 }
 
+static char**
+parse_envlist(PyObject* env, Py_ssize_t *envc_ptr)
+{
+	char **envlist;
+	Py_ssize_t i, pos, envc;
+	PyObject *keys=NULL, *vals=NULL;
+	PyObject *key, *val, *key2, *val2;
+	char *p, *k, *v;
+	size_t len;
+
+	i = PyMapping_Size(env);
+	if (i < 0)
+		return NULL;
+	envlist = PyMem_NEW(char *, i + 1);
+	if (envlist == NULL) {
+		PyErr_NoMemory();
+		return NULL;
+	}
+	envc = 0;
+	keys = PyMapping_Keys(env);
+	vals = PyMapping_Values(env);
+	if (!keys || !vals)
+		goto error;
+	if (!PyList_Check(keys) || !PyList_Check(vals)) {
+		PyErr_Format(PyExc_TypeError,
+			"env.keys() or env.values() is not a list");
+		goto error;
+	}
+
+	for (pos = 0; pos < i; pos++) {
+		key = PyList_GetItem(keys, pos);
+		val = PyList_GetItem(vals, pos);
+		if (!key || !val)
+			goto error;
+
+		if (PyUnicode_FSConverter(key, &key2) == 0)
+			goto error;
+		if (PyUnicode_FSConverter(val, &val2) == 0) {
+			Py_DECREF(key2);
+			goto error;
+		}
+
+#if defined(PYOS_OS2)
+		/* Omit Pseudo-Env Vars that Would Confuse Programs if Passed On */
+		if (stricmp(k, "BEGINLIBPATH") != 0 && stricmp(k, "ENDLIBPATH") != 0) {
+#endif
+		k = PyBytes_AsString(key2);
+		v = PyBytes_AsString(val2);
+		len = PyBytes_GET_SIZE(key2) + PyBytes_GET_SIZE(val2) + 2;
+
+		p = PyMem_NEW(char, len);
+		if (p == NULL) {
+			PyErr_NoMemory();
+			Py_DECREF(key2);
+			Py_DECREF(val2);
+			goto error;
+		}
+		PyOS_snprintf(p, len, "%s=%s", k, v);
+		envlist[envc++] = p;
+		Py_DECREF(key2);
+		Py_DECREF(val2);
+#if defined(PYOS_OS2)
+		}
+#endif
+	}
+	Py_DECREF(vals);
+	Py_DECREF(keys);
+
+	envlist[envc] = 0;
+	*envc_ptr = envc;
+	return envlist;
+
+error:
+	Py_XDECREF(keys);
+	Py_XDECREF(vals);
+	while (--envc >= 0)
+		PyMem_DEL(envlist[envc]);
+	PyMem_DEL(envlist);
+	return NULL;
+}
 
 PyDoc_STRVAR(posix_execve__doc__,
 "execve(path, args, env)\n\n\
@@ -3069,8 +3149,7 @@
 	PyObject *argv, *env;
 	char **argvlist;
 	char **envlist;
-	PyObject *key, *val, *keys=NULL, *vals=NULL;
-	Py_ssize_t i, pos, argc, envc;
+	Py_ssize_t i, argc, envc;
 	PyObject *(*getitem)(PyObject *, Py_ssize_t);
 	Py_ssize_t lastarg = 0;
 
@@ -3118,63 +3197,9 @@
 	lastarg = argc;
 	argvlist[argc] = NULL;
 
-	i = PyMapping_Size(env);
-	if (i < 0)
+	envlist = parse_envlist(env, &envc);
+	if (envlist == NULL)
 		goto fail_1;
-	envlist = PyMem_NEW(char *, i + 1);
-	if (envlist == NULL) {
-		PyErr_NoMemory();
-		goto fail_1;
-	}
-	envc = 0;
-	keys = PyMapping_Keys(env);
-	vals = PyMapping_Values(env);
-	if (!keys || !vals)
-		goto fail_2;
-	if (!PyList_Check(keys) || !PyList_Check(vals)) {
-		PyErr_SetString(PyExc_TypeError,
-			"execve(): env.keys() or env.values() is not a list");
-		goto fail_2;
-	}
-
-	for (pos = 0; pos < i; pos++) {
-		char *p, *k, *v;
-		size_t len;
-
-		key = PyList_GetItem(keys, pos);
-		val = PyList_GetItem(vals, pos);
-		if (!key || !val)
-			goto fail_2;
-
-		if (!PyArg_Parse(
-			    key,
-			    "s;execve() arg 3 contains a non-string key",
-			    &k) ||
-		    !PyArg_Parse(
-			    val,
-			    "s;execve() arg 3 contains a non-string value",
-			    &v))
-		{
-			goto fail_2;
-		}
-
-#if defined(PYOS_OS2)
-        /* Omit Pseudo-Env Vars that Would Confuse Programs if Passed On */
-        if (stricmp(k, "BEGINLIBPATH") != 0 && stricmp(k, "ENDLIBPATH") != 0) {
-#endif
-		len = PyUnicode_GetSize(key) + PyUnicode_GetSize(val) + 2;
-		p = PyMem_NEW(char, len);
-		if (p == NULL) {
-			PyErr_NoMemory();
-			goto fail_2;
-		}
-		PyOS_snprintf(p, len, "%s=%s", k, v);
-		envlist[envc++] = p;
-#if defined(PYOS_OS2)
-    }
-#endif
-	}
-	envlist[envc] = 0;
 
 	execve(path, argvlist, envlist);
 
@@ -3182,14 +3207,11 @@
 
 	(void) posix_error();
 
-  fail_2:
 	while (--envc >= 0)
 		PyMem_DEL(envlist[envc]);
 	PyMem_DEL(envlist);
   fail_1:
 	free_string_array(argvlist, lastarg);
-	Py_XDECREF(vals);
-	Py_XDECREF(keys);
   fail_0:
 	Py_DECREF(opath);
 	return NULL;
@@ -3303,8 +3325,8 @@
 	PyObject *argv, *env;
 	char **argvlist;
 	char **envlist;
-	PyObject *key, *val, *keys=NULL, *vals=NULL, *res=NULL;
-	int mode, pos, envc;
+	PyObject *res = NULL;
+	int mode, envc;
 	Py_ssize_t argc, i;
 	Py_intptr_t spawnval;
 	PyObject *(*getitem)(PyObject *, Py_ssize_t);
@@ -3354,55 +3376,9 @@
 	lastarg = argc;
 	argvlist[argc] = NULL;
 
-	i = PyMapping_Size(env);
-	if (i < 0)
+	envlist = parse_envlist(env, &envc);
+	if (envlist == NULL)
 		goto fail_1;
-	envlist = PyMem_NEW(char *, i + 1);
-	if (envlist == NULL) {
-		PyErr_NoMemory();
-		goto fail_1;
-	}
-	envc = 0;
-	keys = PyMapping_Keys(env);
-	vals = PyMapping_Values(env);
-	if (!keys || !vals)
-		goto fail_2;
-	if (!PyList_Check(keys) || !PyList_Check(vals)) {
-		PyErr_SetString(PyExc_TypeError,
-			"spawnve(): env.keys() or env.values() is not a list");
-		goto fail_2;
-	}
-
-	for (pos = 0; pos < i; pos++) {
-		char *p, *k, *v;
-		size_t len;
-
-		key = PyList_GetItem(keys, pos);
-		val = PyList_GetItem(vals, pos);
-		if (!key || !val)
-			goto fail_2;
-
-		if (!PyArg_Parse(
-			    key,
-			    "s;spawnve() arg 3 contains a non-string key",
-			    &k) ||
-		    !PyArg_Parse(
-			    val,
-			    "s;spawnve() arg 3 contains a non-string value",
-			    &v))
-		{
-			goto fail_2;
-		}
-		len = PyUnicode_GetSize(key) + PyUnicode_GetSize(val) + 2;
-		p = PyMem_NEW(char, len);
-		if (p == NULL) {
-			PyErr_NoMemory();
-			goto fail_2;
-		}
-		PyOS_snprintf(p, len, "%s=%s", k, v);
-		envlist[envc++] = p;
-	}
-	envlist[envc] = 0;
 
 #if defined(PYOS_OS2) && defined(PYCC_GCC)
 	Py_BEGIN_ALLOW_THREADS
@@ -3426,14 +3402,11 @@
 		res = Py_BuildValue("L", (PY_LONG_LONG) spawnval);
 #endif
 
-  fail_2:
 	while (--envc >= 0)
 		PyMem_DEL(envlist[envc]);
 	PyMem_DEL(envlist);
   fail_1:
 	free_string_array(argvlist, lastarg);
-	Py_XDECREF(vals);
-	Py_XDECREF(keys);
   fail_0:
 	Py_DECREF(opath);
 	return res;
@@ -3538,8 +3511,8 @@
 	PyObject *argv, *env;
 	char **argvlist;
 	char **envlist;
-	PyObject *key, *val, *keys=NULL, *vals=NULL, *res=NULL;
-	int mode, i, pos, argc, envc;
+	PyObject *res=NULL;
+	int mode, i, argc, envc;
 	Py_intptr_t spawnval;
 	PyObject *(*getitem)(PyObject *, Py_ssize_t);
 	int lastarg = 0;
@@ -3588,55 +3561,9 @@
 	lastarg = argc;
 	argvlist[argc] = NULL;
 
-	i = PyMapping_Size(env);
-	if (i < 0)
+	envlist = parse_envlist(env, &envc);
+	if (envlist == NULL)
 		goto fail_1;
-	envlist = PyMem_NEW(char *, i + 1);
-	if (envlist == NULL) {
-		PyErr_NoMemory();
-		goto fail_1;
-	}
-	envc = 0;
-	keys = PyMapping_Keys(env);
-	vals = PyMapping_Values(env);
-	if (!keys || !vals)
-		goto fail_2;
-	if (!PyList_Check(keys) || !PyList_Check(vals)) {
-		PyErr_SetString(PyExc_TypeError,
-			"spawnvpe(): env.keys() or env.values() is not a list");
-		goto fail_2;
-	}
-
-	for (pos = 0; pos < i; pos++) {
-		char *p, *k, *v;
-		size_t len;
-
-		key = PyList_GetItem(keys, pos);
-		val = PyList_GetItem(vals, pos);
-		if (!key || !val)
-			goto fail_2;
-
-		if (!PyArg_Parse(
-			    key,
-			    "s;spawnvpe() arg 3 contains a non-string key",
-			    &k) ||
-		    !PyArg_Parse(
-			    val,
-			    "s;spawnvpe() arg 3 contains a non-string value",
-			    &v))
-		{
-			goto fail_2;
-		}
-		len = PyUnicode_GetSize(key) + PyUnicode_GetSize(val) + 2;
-		p = PyMem_NEW(char, len);
-		if (p == NULL) {
-			PyErr_NoMemory();
-			goto fail_2;
-		}
-		PyOS_snprintf(p, len, "%s=%s", k, v);
-		envlist[envc++] = p;
-	}
-	envlist[envc] = 0;
 
 	Py_BEGIN_ALLOW_THREADS
 #if defined(PYCC_GCC)
@@ -3651,14 +3578,11 @@
 	else
 		res = Py_BuildValue("l", (long) spawnval);
 
-  fail_2:
 	while (--envc >= 0)
 		PyMem_DEL(envlist[envc]);
 	PyMem_DEL(envlist);
   fail_1:
 	free_string_array(argvlist, lastarg);
-	Py_XDECREF(vals);
-	Py_XDECREF(keys);
   fail_0:
 	Py_DECREF(opath);
 	return res;