--- a/browser/base/content/test/urlbar/browser.ini
+++ b/browser/base/content/test/urlbar/browser.ini
@@ -108,16 +108,17 @@ subsuite = clipboard
 [browser_urlbar_autoFill_backspaced.js]
 [browser_urlbar_canonize_on_autofill.js]
 [browser_urlbar_blanking.js]
 support-files =
   file_blank_but_not_blank.html
 [browser_urlbar_locationchange_urlbar_edit_dos.js]
 support-files =
   file_urlbar_edit_dos.html
+[browser_urlbar_remove_match.js]
 [browser_urlbar_searchsettings.js]
 [browser_urlbar_search_speculative_connect.js]
 [browser_urlbar_search_speculative_connect_engine.js]
 support-files =
   searchSuggestionEngine2.xml
   searchSuggestionEngine.sjs
 [browser_urlbar_search_speculative_connect_mousedown.js]
 [browser_urlbar_search_no_speculative_connect_with_client_cert.js]

new file mode 100644
--- /dev/null
+++ b/browser/base/content/test/urlbar/browser_urlbar_remove_match.js
@@ -0,0 +1,28 @@
+/* eslint-disable mozilla/no-arbitrary-setTimeout */
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/ */
+
+add_task(async function test_remove_history() {
+  const TEST_URL = "http://remove.me/from_urlbar/";
+  await PlacesTestUtils.addVisits(TEST_URL);
+
+  registerCleanupFunction(async function() {
+    await PlacesUtils.history.clear();
+  });
+
+  let promiseVisitRemoved = PlacesTestUtils.waitForNotification(
+    "onDeleteURI", uri => uri.spec == TEST_URL, "history");
+  await promiseAutocompleteResultPopup("remove.me/from_urlbar");
+  await BrowserTestUtils.waitForCondition(
+    () => gURLBar.popup.richlistbox.children.length > 1 &&
+          gURLBar.popup.richlistbox.children[1].getAttribute("ac-value") == TEST_URL,
+    "Waiting for the result to appear");
+  EventUtils.synthesizeKey("VK_DOWN", {});
+  Assert.equal(gURLBar.popup.richlistbox.selectedIndex, 1);
+  let options = AppConstants.platform == "macosx" ? { shiftKey: true } : {};
+  EventUtils.synthesizeKey("VK_DELETE", options);
+  await promiseVisitRemoved;
+  await BrowserTestUtils.waitForCondition(
+    () => !gURLBar.popup.richlistbox.children.some(c => !c.collapsed && c.getAttribute("ac-value") == TEST_URL),
+    "Waiting for the result to disappear");
+});

--- a/toolkit/components/places/UnifiedComplete.js
+++ b/toolkit/components/places/UnifiedComplete.js
@@ -783,28 +783,25 @@ function looksLikeUrl(str, ignoreAlphanu
  *          window outside of permanent private-browsing mode.  The search
  *          should exclude privacy-sensitive results as appropriate.
  *        * private-window: The search is taking place in a private window,
  *          possibly in permanent private-browsing mode.  The search
  *          should exclude privacy-sensitive results as appropriate.
  *        * user-context-id: The userContextId of the selected tab.
  * @param autocompleteListener
  *        An nsIAutoCompleteObserver.
- * @param resultListener
- *        An nsIAutoCompleteSimpleResultListener.
  * @param autocompleteSearch
  *        An nsIAutoCompleteSearch.
  * @param prohibitSearchSuggestions
  *        Whether search suggestions are allowed for this search.
  * @param [optional] previousResult
  *        The result object from the previous search. if available.
  */
 function Search(searchString, searchParam, autocompleteListener,
-                resultListener, autocompleteSearch, prohibitSearchSuggestions,
-                previousResult) {
+                autocompleteSearch, prohibitSearchSuggestions, previousResult) {
   // We want to store the original string for case sensitive searches.
   this._originalSearchString = searchString;
   this._trimmedOriginalSearchString = searchString.trim();
   let strippedOriginalSearchString =
     stripPrefix(this._trimmedOriginalSearchString.toLowerCase());
   this._searchString =
     textURIService.unEscapeURIForUI("UTF-8", strippedOriginalSearchString);
 
@@ -839,17 +836,26 @@ function Search(searchString, searchPara
   this._autocompleteSearch = autocompleteSearch;
 
   // Create a new result to add eventual matches.  Note we need a result
   // regardless having matches.
   let result = previousResult ||
                Cc["@mozilla.org/autocomplete/simple-result;1"]
                  .createInstance(Ci.nsIAutoCompleteSimpleResult);
   result.setSearchString(searchString);
-  result.setListener(resultListener);
+  result.setListener({
+    onValueRemoved(result, spec, removeFromDB) {
+      if (removeFromDB) {
+        PlacesUtils.history.remove(spec).catch(Cu.reportError);
+      }
+    },
+    QueryInterface: XPCOMUtils.generateQI([
+      Ci.nsIAutoCompleteSimpleResultListener
+    ])
+  });
   // Will be set later, if needed.
   result.setDefaultIndex(-1);
   this._result = result;
 
   this._previousSearchMatchTypes = [];
   for (let i = 0; previousResult && i < previousResult.matchCount; ++i) {
     let style = previousResult.getStyleAt(i);
     if (style.includes("heuristic")) {
@@ -2369,17 +2375,16 @@ Search.prototype = {
     let resultCode = this._currentMatchCount ? "RESULT_SUCCESS" : "RESULT_NOMATCH";
     if (searchOngoing) {
       resultCode += "_ONGOING";
     }
     result.setSearchResult(Ci.nsIAutoCompleteResult[resultCode]);
     this._listener.onSearchResult(this._autocompleteSearch, result);
     if (!searchOngoing) {
       // Break possible cycles.
-      this._result.setListener(null);
       this._listener = null;
       this._autocompleteSearch = null;
     }
   },
 }
 
 // UnifiedComplete class
 // component @mozilla.org/autocomplete/search;1?name=unifiedcomplete
@@ -2485,17 +2490,16 @@ UnifiedComplete.prototype = {
 
     // If the previous search didn't fetch enough search suggestions, it's
     // unlikely a longer text would do.
     let prohibitSearchSuggestions =
       !!this._lastLowResultsSearchSuggestion &&
       searchString.length > this._lastLowResultsSearchSuggestion.length &&
       searchString.startsWith(this._lastLowResultsSearchSuggestion);
 
-
     // We don't directly reuse the controller provided previousResult because:
     //  * it is only populated when the new searchString is an extension of the
     //    previous one. We want to handle the backspace case too.
     //  * Bookmarks may be titled differently than history and we want to show
     //    the right title.  For example a "foo" titled page could be bookmarked
     //    as "foox", typing "foo" followed by "x" would show the history result
     //    from the previous search (See bug 412730).
     //  * Adaptive History means a result may appear even if the previous string
@@ -2519,17 +2523,17 @@ UnifiedComplete.prototype = {
                            (previousSearchString.includes(searchString) ||
                             searchString.includes(previousSearchString));
       if (insertMethod == INSERTMETHOD.MERGE || stringsRelated) {
         previousResult = result;
       }
     }
 
     this._currentSearch = new Search(searchString, searchParam, listener,
-                                     this, this, prohibitSearchSuggestions,
+                                     this, prohibitSearchSuggestions,
                                      previousResult);
 
     // If we are not enabled, we need to return now.  Notice we need an empty
     // result regardless, so we still create the Search object.
     if (!Prefs.get("autocomplete.enabled")) {
       this.finishSearch(true);
       return;
     }
@@ -2588,24 +2592,16 @@ UnifiedComplete.prototype = {
     // If onSearchComplete immediately starts a new search it will set a new
     // _currentSearch, and on return the execution will continue here, after
     // notifyResults.
     // Thus, ensure that notifyResults is the last call in this method,
     // otherwise you might be touching the wrong search.
     search.notifyResults(false);
   },
 
-  // nsIAutoCompleteSimpleResultListener
-
-  onValueRemoved(result, spec, removeFromDB) {
-    if (removeFromDB) {
-      PlacesUtils.history.remove(spec).catch(Cu.reportError);
-    }
-  },
-
   // nsIAutoCompleteSearchDescriptor
 
   get searchType() {
     return Ci.nsIAutoCompleteSearchDescriptor.SEARCH_TYPE_IMMEDIATE;
   },
 
   get clearingAutoFillSearchesAgain() {
     return true;
@@ -2614,17 +2610,16 @@ UnifiedComplete.prototype = {
   // nsISupports
 
   classID: Components.ID("f964a319-397a-4d21-8be6-5cdd1ee3e3ae"),
 
   _xpcom_factory: XPCOMUtils.generateSingletonFactory(UnifiedComplete),
 
   QueryInterface: XPCOMUtils.generateQI([
     Ci.nsIAutoCompleteSearch,
-    Ci.nsIAutoCompleteSimpleResultListener,
     Ci.nsIAutoCompleteSearchDescriptor,
     Ci.mozIPlacesAutoComplete,
     Ci.nsIObserver,
     Ci.nsISupportsWeakReference
   ])
 };
 
 this.NSGetFactory = XPCOMUtils.generateNSGetFactory([UnifiedComplete]);

deleted file mode 100644
--- a/toolkit/components/places/tests/unifiedcomplete/test_autocomplete_on_value_removed_479089.js
+++ /dev/null
@@ -1,42 +0,0 @@
-/* -*- indent-tabs-mode: nil; js-indent-level: 2 -*- */
-/* vim:set ts=2 sw=2 sts=2 et: */
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-/*
- * Need to test that removing a page from autocomplete actually removes a page
- * Description From  Shawn Wilsher :sdwilsh   2009-02-18 11:29:06 PST
- * We don't test the code path of onValueRemoved
- * for the autocomplete implementation
- * Bug 479089
- */
-
-function promiseURIDeleted(testURI) {
-  return new Promise(resolve => {
-    let obs = new NavHistoryObserver();
-    obs.onDeleteURI = (uri, guid, reason) => {
-      PlacesUtils.history.removeObserver(obs);
-      Assert.equal(uri.spec, testURI.spec, "Deleted URI should be the expected one");
-      resolve();
-    };
-    PlacesUtils.history.addObserver(obs);
-  });
-}
-
-add_task(async function test_autocomplete_on_value_removed() {
-  let listener = Cc["@mozilla.org/autocomplete/search;1?name=unifiedcomplete"].
-                 getService(Components.interfaces.nsIAutoCompleteSimpleResultListener);
-
-  let testUri = NetUtil.newURI("http://foo.mozilla.com/");
-  await PlacesTestUtils.addVisits({
-    uri: testUri,
-    referrer: uri("http://mozilla.com/")
-  });
-
-  let promise = promiseURIDeleted(testUri);
-  // call the untested code path
-  listener.onValueRemoved(null, testUri.spec, true);
-
-  await promise;
-});

--- a/toolkit/components/places/tests/unifiedcomplete/xpcshell.ini
+++ b/toolkit/components/places/tests/unifiedcomplete/xpcshell.ini
@@ -7,17 +7,16 @@ support-files =
   !/toolkit/components/places/tests/favicons/favicon-normal16.png
 
 [test_416211.js]
 [test_416214.js]
 [test_417798.js]
 [test_418257.js]
 [test_422277.js]
 [test_autocomplete_functional.js]
-[test_autocomplete_on_value_removed_479089.js]
 [test_autofill_default_behavior.js]
 [test_avoid_middle_complete.js]
 [test_avoid_stripping_to_empty_tokens.js]
 [test_casing.js]
 [test_do_not_trim.js]
 [test_download_embed_bookmarks.js]
 [test_dupe_urls.js]
 [test_empty_search.js]