--- a/services/sync/modules/engines/history.js
+++ b/services/sync/modules/engines/history.js
@@ -321,24 +321,16 @@ HistoryStore.prototype = {
     PlacesUtils.history.removePage(uri);
     this._log.trace("Removed page: " + [record.id, page.url, page.title]);
   },
 
   itemExists: function HistStore_itemExists(id) {
     return !!this._findURLByGUID(id);
   },
 
-  urlExists: function HistStore_urlExists(url) {
-    if (typeof(url) == "string") {
-      url = Utils.makeURI(url);
-    }
-    // Don't call isVisited on a null URL to work around crasher bug 492442.
-    return url ? PlacesUtils.history.isVisited(url) : false;
-  },
-
   createRecord: function createRecord(id, collection) {
     let foo = this._findURLByGUID(id);
     let record = new HistoryRec(collection, id);
     if (foo) {
       record.histUri = foo.url;
       record.title = foo.title;
       record.sortindex = foo.frecency;
       record.visits = this._getVisits(record.histUri);

--- a/services/sync/tests/unit/test_corrupt_keys.js
+++ b/services/sync/tests/unit/test_corrupt_keys.js
@@ -6,18 +6,19 @@ Cu.import("resource://services-sync/cons
 Cu.import("resource://services-sync/engines.js");
 Cu.import("resource://services-sync/engines/tabs.js");
 Cu.import("resource://services-sync/engines/history.js");
 Cu.import("resource://services-sync/record.js");
 Cu.import("resource://services-sync/service.js");
 Cu.import("resource://services-sync/status.js");
 Cu.import("resource://services-sync/util.js");
 Cu.import("resource://testing-common/services/sync/utils.js");
+Cu.import("resource://gre/modules/commonjs/promise/core.js");
 
-add_test(function test_locally_changed_keys() {
+add_task(function test_locally_changed_keys() {
   let passphrase = "abcdeabcdeabcdeabcdeabcdea";
 
   let hmacErrorCount = 0;
   function counting(f) {
     return function() {
       hmacErrorCount++;
       return f.call(this);
     };
@@ -140,21 +141,21 @@ add_test(function test_locally_changed_k
     _("HMAC error count: " + hmacErrorCount);
     // Now syncing should succeed, after one HMAC error.
     Service.sync();
     do_check_eq(hmacErrorCount, 1);
     _("Keys now: " + Service.collectionKeys.keyForCollection("history").keyPair);
 
     // And look! We downloaded history!
     let store = Service.engineManager.get("history")._store;
-    do_check_true(store.urlExists("http://foo/bar?record-no--0"));
-    do_check_true(store.urlExists("http://foo/bar?record-no--1"));
-    do_check_true(store.urlExists("http://foo/bar?record-no--2"));
-    do_check_true(store.urlExists("http://foo/bar?record-no--3"));
-    do_check_true(store.urlExists("http://foo/bar?record-no--4"));
+    do_check_true(yield promiseIsURIVisited("http://foo/bar?record-no--0"));
+    do_check_true(yield promiseIsURIVisited("http://foo/bar?record-no--1"));
+    do_check_true(yield promiseIsURIVisited("http://foo/bar?record-no--2"));
+    do_check_true(yield promiseIsURIVisited("http://foo/bar?record-no--3"));
+    do_check_true(yield promiseIsURIVisited("http://foo/bar?record-no--4"));
     do_check_eq(hmacErrorCount, 1);
 
     _("Busting some new server values.");
     // Now what happens if we corrupt the HMAC on the server?
     for (let i = 5; i < 10; i++) {
       let id = 'record-no--' + i;
       let modified = 1 + (Date.now() / 1000);
 
@@ -183,26 +184,43 @@ add_test(function test_locally_changed_k
     Service.lastHMACEvent = 0;
 
     _("Syncing...");
     Service.sync();
     _("Keys now: " + Service.collectionKeys.keyForCollection("history").keyPair);
     _("Server keys have been updated, and we skipped over 5 more HMAC errors without adjusting history.");
     do_check_true(johndoe.modified("crypto") > old_key_time);
     do_check_eq(hmacErrorCount, 6);
-    do_check_false(store.urlExists("http://foo/bar?record-no--5"));
-    do_check_false(store.urlExists("http://foo/bar?record-no--6"));
-    do_check_false(store.urlExists("http://foo/bar?record-no--7"));
-    do_check_false(store.urlExists("http://foo/bar?record-no--8"));
-    do_check_false(store.urlExists("http://foo/bar?record-no--9"));
-
+    do_check_false(yield promiseIsURIVisited("http://foo/bar?record-no--5"));
+    do_check_false(yield promiseIsURIVisited("http://foo/bar?record-no--6"));
+    do_check_false(yield promiseIsURIVisited("http://foo/bar?record-no--7"));
+    do_check_false(yield promiseIsURIVisited("http://foo/bar?record-no--8"));
+    do_check_false(yield promiseIsURIVisited("http://foo/bar?record-no--9"));
   } finally {
     Svc.Prefs.resetBranch("");
-    server.stop(run_next_test);
+    let deferred = Promise.defer();
+    server.stop(deferred.resolve);
+    yield deferred.promise;
   }
 });
 
 function run_test() {
   let logger = Log4Moz.repository.rootLogger;
   Log4Moz.repository.rootLogger.addAppender(new Log4Moz.DumpAppender());
 
   run_next_test();
 }
+
+/**
+ * Asynchronously check a url is visited.
+ * @param url the url
+ * @return {Promise}
+ * @resolves When the check has been added successfully.
+ * @rejects JavaScript exception.
+ */
+function promiseIsURIVisited(url) {
+  let deferred = Promise.defer();
+  PlacesUtils.asyncHistory.isURIVisited(Utils.makeURI(url), function(aURI, aIsVisited) {
+    deferred.resolve(aIsVisited);
+  });
+
+  return deferred.promise;
+}