--- a/netwerk/cookie/nsCookieService.cpp
+++ b/netwerk/cookie/nsCookieService.cpp
@@ -53,29 +53,31 @@
 #include "nsCRT.h"
 #include "prprf.h"
 #include "nsNetUtil.h"
 #include "nsNetCID.h"
 #include "nsISimpleEnumerator.h"
 #include "nsIInputStream.h"
 #include "nsAppDirectoryServiceDefs.h"
 #include "nsNetCID.h"
+#include "mozilla/dom/Promise.h"
 #include "mozilla/storage.h"
 #include "mozilla/AutoRestore.h"
 #include "mozilla/FileUtils.h"
 #include "mozilla/ScopeExit.h"
 #include "mozilla/StaticPrefs_network.h"
 #include "mozilla/StaticPrefs_privacy.h"
 #include "mozilla/Telemetry.h"
 #include "mozilla/TextUtils.h"
 #include "nsIConsoleService.h"
 #include "nsTPriorityQueue.h"
 #include "nsVariant.h"
 
 using namespace mozilla;
+using namespace mozilla::dom;
 using namespace mozilla::net;
 
 // Create key from baseDomain that will access the default cookie namespace.
 // TODO: When we figure out what the API will look like for nsICookieManager{2}
 // on content processes (see bug 777620), change to use the appropriate app
 // namespace.  For now those IDLs aren't supported on child processes.
 #define DEFAULT_APP_KEY(baseDomain) nsCookieKey(baseDomain, OriginAttributes())
 
@@ -4858,16 +4860,98 @@ nsresult nsCookieService::RemoveCookiesF
     }
   }
   rv = transaction.Commit();
   MOZ_ASSERT(NS_SUCCEEDED(rv));
 
   return NS_OK;
 }
 
+namespace {
+
+class RemoveAllSinceRunnable : public Runnable {
+ public:
+  typedef nsTArray<nsCOMPtr<nsICookie>> CookieArray;
+  RemoveAllSinceRunnable(Promise* aPromise, nsCookieService* aSelf,
+                         CookieArray&& aCookieArray, int64_t aSinceWhen)
+      : Runnable("RemoveAllSinceRunnable"),
+        mPromise(aPromise),
+        mSelf(aSelf),
+        mList(std::move(aCookieArray)),
+        mIndex(0),
+        mSinceWhen(aSinceWhen) {}
+
+  NS_IMETHODIMP Run() {
+    RemoveSome();
+
+    if (mIndex < mList.Length()) {
+      return NS_DispatchToCurrentThread(this);
+    } else {
+      mPromise->MaybeResolveWithUndefined();
+    }
+    return NS_OK;
+  }
+
+ private:
+  void RemoveSome() {
+    for (CookieArray::size_type iter = 0;
+         iter < kYieldPeriod && mIndex < mList.Length(); ++mIndex, ++iter) {
+      nsCookie* cookie = static_cast<nsCookie*>(mList[mIndex].get());
+      if (cookie->CreationTime() > mSinceWhen &&
+          NS_FAILED(mSelf->Remove(cookie->Host(), cookie->OriginAttributesRef(),
+                                  cookie->Name(), cookie->Path()))) {
+        continue;
+      }
+    }
+  }
+
+ private:
+  RefPtr<Promise> mPromise;
+  RefPtr<nsCookieService> mSelf;
+  CookieArray mList;
+  CookieArray::size_type mIndex;
+  int64_t mSinceWhen;
+  static const CookieArray::size_type kYieldPeriod = 10;
+};
+
+}  // namespace
+
+NS_IMETHODIMP
+nsCookieService::RemoveAllSince(int64_t aSinceWhen, JSContext* aCx,
+                                Promise** aRetVal) {
+  nsIGlobalObject* globalObject = xpc::CurrentNativeGlobal(aCx);
+  if (NS_WARN_IF(!globalObject)) {
+    return NS_ERROR_UNEXPECTED;
+  }
+
+  ErrorResult result;
+  RefPtr<Promise> promise = Promise::Create(globalObject, result);
+  if (NS_WARN_IF(result.Failed())) {
+    return result.StealNSResult();
+  }
+
+  EnsureReadComplete(true);
+
+  typedef RemoveAllSinceRunnable::CookieArray CookieArray;
+  CookieArray cookieList(mDBState->cookieCount);
+  for (auto iter = mDBState->hostTable.Iter(); !iter.Done(); iter.Next()) {
+    const nsCookieEntry::ArrayType& cookies = iter.Get()->GetCookies();
+    for (nsCookieEntry::IndexType i = 0; i < cookies.Length(); ++i) {
+      cookieList.AppendElement(cookies[i]);
+    }
+  }
+
+  RefPtr<RemoveAllSinceRunnable> runMe = new RemoveAllSinceRunnable(
+      promise, this, std::move(cookieList), aSinceWhen);
+
+  promise.forget(aRetVal);
+
+  return runMe->Run();
+}
+
 // find an secure cookie specified by host and name
 bool nsCookieService::FindSecureCookie(const nsCookieKey& aKey,
                                        nsCookie* aCookie) {
   nsCookieEntry* entry = mDBState->hostTable.GetEntry(aKey);
   if (!entry) return false;
 
   const nsCookieEntry::ArrayType& cookies = entry->GetCookies();
   for (nsCookieEntry::IndexType i = 0; i < cookies.Length(); ++i) {

--- a/netwerk/cookie/nsCookieService.h
+++ b/netwerk/cookie/nsCookieService.h
@@ -227,16 +227,23 @@ class nsCookieService final : public nsI
                         bool aIsTrackingResource,
                         bool aIsSocialTrackingResource,
                         bool aFirstPartyStorageAccessGranted,
                         uint32_t aRejectedReason, bool aIsSafeTopLevelNav,
                         bool aIsSameSiteForeign, bool aHttpBound,
                         const OriginAttributes& aOriginAttrs,
                         nsTArray<nsCookie*>& aCookieList);
 
+  /**
+   * This method is a helper that allows calling nsICookieManager::Remove()
+   * with OriginAttributes parameter.
+   */
+  nsresult Remove(const nsACString& aHost, const OriginAttributes& aAttrs,
+                  const nsACString& aName, const nsACString& aPath);
+
  protected:
   virtual ~nsCookieService();
 
   void PrefChanged(nsIPrefBranch* aPrefBranch);
   void InitDBStates();
   OpenDBResult TryInitDB(bool aDeleteExistingDB);
   void InitDBConn();
   nsresult InitDBConnInternal();
@@ -332,24 +339,16 @@ class nsCookieService final : public nsI
 
   nsresult GetCookiesWithOriginAttributes(
       const mozilla::OriginAttributesPattern& aPattern,
       const nsCString& aBaseDomain, nsTArray<RefPtr<nsICookie>>& aResult);
   nsresult RemoveCookiesWithOriginAttributes(
       const mozilla::OriginAttributesPattern& aPattern,
       const nsCString& aBaseDomain);
 
-  /**
-   * This method is a helper that allows calling nsICookieManager::Remove()
-   * with OriginAttributes parameter.
-   * NOTE: this could be added to a public interface if we happen to need it.
-   */
-  nsresult Remove(const nsACString& aHost, const OriginAttributes& aAttrs,
-                  const nsACString& aName, const nsACString& aPath);
-
  protected:
   nsresult RemoveCookiesFromExactHost(
       const nsACString& aHost,
       const mozilla::OriginAttributesPattern& aPattern);
 
   // cached members.
   nsCOMPtr<nsICookiePermission> mPermissionService;
   nsCOMPtr<mozIThirdPartyUtil> mThirdPartyUtil;

--- a/netwerk/cookie/nsICookieManager.idl
+++ b/netwerk/cookie/nsICookieManager.idl
@@ -232,9 +232,20 @@ interface nsICookieManager : nsISupports
   /**
    * Remove all the cookies whose origin attributes matches aPattern and the
    * host is exactly aHost (without subdomain matching).
    *
    * @param aHost the host to match
    * @param aPattern origin attribute pattern in JSON format
    */
   void removeCookiesFromExactHost(in AUTF8String aHost, in AString aPattern);
+
+  /**
+   * Removes all cookies that were created on or after aSinceWhen, and returns
+   * a Promise which will be resolved when the last such cookie has been
+   * removed.
+   *
+   * @param aSinceWhen the starting point in time after which no cookies should
+   *        be created when the Promise returned from this method is resolved.
+   */
+  [implicit_jscontext]
+  Promise removeAllSince(in int64_t aSinceWhen);
 };

--- a/toolkit/components/cleardata/ClearDataService.jsm
+++ b/toolkit/components/cleardata/ClearDataService.jsm
@@ -68,57 +68,25 @@ const CookieCleaner = {
         aHost,
         JSON.stringify(aOriginAttributes)
       );
       aResolve();
     });
   },
 
   deleteByRange(aFrom, aTo) {
-    let enumerator = Services.cookies.enumerator;
-    return this._deleteInternal(
-      enumerator,
-      aCookie => aCookie.creationTime > aFrom
-    );
+    return Services.cookies.removeAllSince(aFrom);
   },
 
   deleteAll() {
     return new Promise(aResolve => {
       Services.cookies.removeAll();
       aResolve();
     });
   },
-
-  _deleteInternal(aEnumerator, aCb) {
-    // A number of iterations after which to yield time back to the system.
-    const YIELD_PERIOD = 10;
-
-    return new Promise((aResolve, aReject) => {
-      let count = 0;
-      for (let cookie of aEnumerator) {
-        if (aCb(cookie)) {
-          Services.cookies.remove(
-            cookie.host,
-            cookie.name,
-            cookie.path,
-            cookie.originAttributes
-          );
-          // We don't want to block the main-thread.
-          if (++count % YIELD_PERIOD == 0) {
-            setTimeout(() => {
-              this._deleteInternal(aEnumerator, aCb).then(aResolve, aReject);
-            }, 0);
-            return;
-          }
-        }
-      }
-
-      aResolve();
-    });
-  },
 };
 
 const CertCleaner = {
   deleteByHost(aHost, aOriginAttributes) {
     let overrideService = Cc["@mozilla.org/security/certoverride;1"].getService(
       Ci.nsICertOverrideService
     );
     return new Promise(aResolve => {