diff --git a/Modules/timemodule.c b/Modules/timemodule.c
index 45002a1..8ce6667 100644
--- a/Modules/timemodule.c
+++ b/Modules/timemodule.c
@@ -377,13 +377,17 @@
 	PyObject *tup = NULL;
 	struct tm buf;
 	const char *fmt;
+	PyObject *format;
 	size_t fmtlen, buflen;
 	char *outbuf = 0;
 	size_t i;
 
 	memset((void *) &buf, '\0', sizeof(buf));
 
-	if (!PyArg_ParseTuple(args, "s|O:strftime", &fmt, &tup))
+	/* Will always expect a unicode string to be passed as format.
+	   Given that there's no str type anymore in py3k this seems safe.
+	*/
+	if (!PyArg_ParseTuple(args, "U|O:strftime", &format, &tup))
 		return NULL;
 
 	if (tup == NULL) {
@@ -458,6 +462,9 @@
             return NULL;
         }
 
+    /* Convert the unicode string to an ascii one */
+    fmt = PyUnicode_AsString(format);
+
 	fmtlen = strlen(fmt);
 
 	/* I hate these functions that presume you know how big the output
@@ -535,7 +542,7 @@
 	p = asctime(&buf);
 	if (p[24] == '\n')
 		p[24] = '\0';
-	return PyString_FromString(p);
+	return PyUnicode_FromString(p);
 }
 
 PyDoc_STRVAR(asctime_doc,
@@ -571,7 +578,7 @@
 	}
 	if (p[24] == '\n')
 		p[24] = '\0';
-	return PyString_FromString(p);
+	return PyUnicode_FromString(p);
 }
 
 PyDoc_STRVAR(ctime_doc,