--- a/testing/xpcshell/head.js
+++ b/testing/xpcshell/head.js
@@ -18,16 +18,17 @@ var _pendingTimers = [];
 var _profileInitialized = false;
 
 // Register the testing-common resource protocol early, to have access to its
 // modules.
 _register_modules_protocol_handler();
 
 var _Promise = Components.utils.import("resource://gre/modules/Promise.jsm", {}).Promise;
 var _PromiseTestUtils = Components.utils.import("resource://testing-common/PromiseTestUtils.jsm", {}).PromiseTestUtils;
+var _Task = Components.utils.import("resource://gre/modules/Task.jsm", {}).Task;
 Components.utils.importGlobalProperties(["XMLHttpRequest"]);
 
 // Support a common assertion library, Assert.jsm.
 var AssertCls = Components.utils.import("resource://testing-common/Assert.jsm", null).Assert;
 // Pass a custom report function for xpcshell-test style reporting.
 var Assert = new AssertCls(function(err, message, stack) {
   if (err) {
     do_report_result(false, err.message, err.stack);
@@ -595,37 +596,32 @@ function _execute_test() {
     }
     _testLogger.error(_exception_message(ex),
                       {
                         stack: _format_stack(stack),
                         source_file: filename
                       });
   };
 
-  let func;
-  while ((func = _cleanupFunctions.pop())) {
-    let result;
-    try {
-      result = func();
-    } catch (ex) {
-      reportCleanupError(ex);
-      continue;
-    }
-    if (result && typeof result == "object"
-        && "then" in result && typeof result.then == "function") {
-      // This is a promise, wait until it is satisfied before proceeding
-      let complete = false;
-      let promise = result.then(null, reportCleanupError);
-      promise = promise.then(() => complete = true);
-      let thr = Components.classes["@mozilla.org/thread-manager;1"]
-                  .getService().currentThread;
-      while (!complete) {
-        thr.processNextEvent(true);
+  let complete = _cleanupFunctions.length == 0;
+  _Task.spawn(function*() {
+    for (let func of _cleanupFunctions.reverse()) {
+      try {
+        yield func();
+      } catch (ex) {
+        reportCleanupError(ex);
       }
     }
+    _cleanupFunctions = [];
+  }.bind(this)).catch(reportCleanupError)
+               .then(() => complete = true);
+  let thr = Components.classes["@mozilla.org/thread-manager;1"]
+                      .getService().currentThread;
+  while (!complete) {
+    thr.processNextEvent(true);
   }
 
   // Restore idle service to avoid leaks.
   _fakeIdleService.deactivate();
 
   if (_profileInitialized) {
     // Since we have a profile, we will notify profile shutdown topics at
     // the end of the current test, to ensure correct cleanup on shutdown.
@@ -1514,17 +1510,16 @@ function add_task(funcOrProperties, func
     _gTests.push([funcOrProperties, func]);
   } else {
     do_throw("add_task() should take a function or an object and a function");
   }
 }
 add_task.only = _add_only.bind(undefined, add_task);
 add_task.skip = _add_skip.bind(undefined, add_task);
 
-var _Task = Components.utils.import("resource://gre/modules/Task.jsm", {}).Task;
 _Task.Debugging.maintainStack = true;
 
 
 /**
  * Runs the next test function from the list of async tests.
  */
 var _gRunningTest = null;
 var _gTestIndex = 0; // The index of the currently running test.

--- a/testing/xpcshell/selftest.py
+++ b/testing/xpcshell/selftest.py
@@ -296,22 +296,32 @@ ASYNC_CLEANUP = '''
 function run_test() {
   Components.utils.import("resource://gre/modules/Promise.jsm", this);
 
   // The list of checkpoints in the order we encounter them.
   let checkpoints = [];
 
   // Cleanup tasks, in reverse order
   do_register_cleanup(function cleanup_checkout() {
-    do_check_eq(checkpoints.join(""), "1234");
+    do_check_eq(checkpoints.join(""), "123456");
     do_print("At this stage, the test has succeeded");
     do_throw("Throwing an error to force displaying the log");
   });
 
   do_register_cleanup(function sync_cleanup_2() {
+    checkpoints.push(6);
+  });
+
+  do_register_cleanup(async function async_cleanup_4() {
+    await undefined;
+    checkpoints.push(5);
+  });
+
+  do_register_cleanup(function* async_cleanup_3() {
+    yield undefined;
     checkpoints.push(4);
   });
 
   do_register_cleanup(function async_cleanup_2() {
     let deferred = Promise.defer();
     do_execute_soon(deferred.resolve);
     return deferred.promise.then(function() {
       checkpoints.push(3);
@@ -1196,23 +1206,22 @@ add_test({
         self.writeFile("test_verbose.js", ADD_TEST_VERBOSE)
         self.writeManifest([("test_verbose.js", "verbose = true")])
 
         self.assertTestResult(True)
         self.assertInLog("a message from do_print")
 
     def testAsyncCleanup(self):
         """
-        Check that do_register_cleanup handles nicely cleanup tasks that
-        return a promise
+        Check that do_register_cleanup handles nicely async cleanup tasks
         """
         self.writeFile("test_asyncCleanup.js", ASYNC_CLEANUP)
         self.writeManifest(["test_asyncCleanup.js"])
         self.assertTestResult(False)
-        self.assertInLog("\"1234\" == \"1234\"")
+        self.assertInLog("\"123456\" == \"123456\"")
         self.assertInLog("At this stage, the test has succeeded")
         self.assertInLog("Throwing an error to force displaying the log")
 
     def testNoRunTestAddTest(self):
         """
         Check that add_test() works fine without run_test() in the test file.
         """
         self.writeFile("test_noRunTestAddTest.js", NO_RUN_TEST_ADD_TEST)