--- a/toolkit/components/places/UnifiedComplete.js
+++ b/toolkit/components/places/UnifiedComplete.js
@@ -581,28 +581,16 @@ XPCOMUtils.defineLazyGetter(this, "Prefi
 
 XPCOMUtils.defineLazyGetter(this, "ProfileAgeCreatedPromise", () => {
   return (new ProfileAge(null, null)).created;
 });
 
 // Helper functions
 
 /**
- * Used to unescape encoded URI strings and drop information that we do not
- * care about.
- *
- * @param spec
- *        The text to unescape and modify.
- * @return the modified spec.
- */
-function fixupSearchText(spec) {
-  return textURIService.unEscapeURIForUI("UTF-8", stripPrefix(spec));
-}
-
-/**
  * Generates the tokens used in searching from a given string.
  *
  * @param searchString
  *        The string to generate tokens from.
  * @return an array of tokens.
  * @note Calling split on an empty string will return an array containing one
  *       empty string.  We don't want that, as it'll break our logic, so return
  *       an empty array then.
@@ -635,26 +623,28 @@ function stripPrefix(spec) {
   return spec;
 }
 
 /**
  * Strip http and trailing separators from a spec.
  *
  * @param spec
  *        The text to modify.
+ * @param trimSlash
+ *        Whether to trim the trailing slash.
  * @return the modified spec.
  */
-function stripHttpAndTrim(spec) {
+function stripHttpAndTrim(spec, trimSlash = true) {
   if (spec.startsWith("http://")) {
     spec = spec.slice(7);
   }
   if (spec.endsWith("?")) {
     spec = spec.slice(0, -1);
   }
-  if (spec.endsWith("/")) {
+  if (trimSlash && spec.endsWith("/")) {
     spec = spec.slice(0, -1);
   }
   return spec;
 }
 
 /**
  * Returns the key to be used for a match in a map for the purposes of removing
  * duplicate entries - any 2 URLs that should be considered the same should
@@ -737,17 +727,26 @@ function looksLikeUrl(str, ignoreAlphanu
  * @param prohibitSearchSuggestions
  *        Whether search suggestions are allowed for this search.
  */
 function Search(searchString, searchParam, autocompleteListener,
                 resultListener, autocompleteSearch, prohibitSearchSuggestions) {
   // We want to store the original string for case sensitive searches.
   this._originalSearchString = searchString;
   this._trimmedOriginalSearchString = searchString.trim();
-  this._searchString = fixupSearchText(this._trimmedOriginalSearchString.toLowerCase());
+  let strippedOriginalSearchString =
+    stripPrefix(this._trimmedOriginalSearchString.toLowerCase());
+  this._searchString =
+    textURIService.unEscapeURIForUI("UTF-8", strippedOriginalSearchString);
+
+  // The protocol and the host are lowercased by nsIURI, so it's fine to
+  // lowercase the typed prefix, to add it back to the results later.
+  this._strippedPrefix = this._trimmedOriginalSearchString.slice(
+    0, this._trimmedOriginalSearchString.length - strippedOriginalSearchString.length
+  ).toLowerCase();
 
   this._matchBehavior = Prefs.matchBehavior;
   // Set the default behavior for this search.
   this._behavior = this._searchString ? Prefs.defaultBehavior
                                       : Prefs.emptySearchDefaultBehavior;
 
   let params = new Set(searchParam.split(" "));
   this._enableActions = params.has("enable-actions");
@@ -757,29 +756,16 @@ function Search(searchString, searchPara
 
   let userContextId = searchParam.match(REGEXP_USER_CONTEXT_ID);
   this._userContextId = userContextId ?
                           parseInt(userContextId[1], 10) :
                           Ci.nsIScriptSecurityManager.DEFAULT_USER_CONTEXT_ID;
 
   this._searchTokens =
     this.filterTokens(getUnfilteredSearchTokens(this._searchString));
-  // The protocol and the host are lowercased by nsIURI, so it's fine to
-  // lowercase the typed prefix, to add it back to the results later.
-  this._strippedPrefix = this._trimmedOriginalSearchString.slice(
-    0, this._trimmedOriginalSearchString.length - this._searchString.length
-  ).toLowerCase();
-  // The URIs in the database are fixed-up, so we can match on a lowercased
-  // host, but the path must be matched in a case sensitive way.
-  let pathIndex =
-    this._trimmedOriginalSearchString.indexOf("/", this._strippedPrefix.length);
-  this._autofillUrlSearchString = fixupSearchText(
-    this._trimmedOriginalSearchString.slice(0, pathIndex).toLowerCase() +
-    this._trimmedOriginalSearchString.slice(pathIndex)
-  );
 
   this._prohibitSearchSuggestions = prohibitSearchSuggestions;
 
   this._listener = autocompleteListener;
   this._autocompleteSearch = autocompleteSearch;
 
   // Create a new result to add eventual matches.  Note we need a result
   // regardless having matches.
@@ -1084,17 +1070,16 @@ Search.prototype = {
 
   _matchPrefillSiteForAutofill() {
     if (!Prefs.prefillSitesEnabled)
       return false;
     for (let site of PrefillSiteStorage.sites) {
       if (site.uri.host.startsWith(this._searchString)) {
         let match = {
           value: stripPrefix(site.uri.spec),
-          comment: site.title,
           style: "autofill",
           finalCompleteValue: site.uri.spec,
           frecency: FRECENCY_DEFAULT,
         };
         this._result.setDefaultIndex(0);
         this._addMatch(match);
         return true;
       }
@@ -1620,16 +1605,30 @@ Search.prototype = {
   },
 
   _addMatch(match) {
     // A search could be canceled between a query start and its completion,
     // in such a case ensure we won't notify any result for it.
     if (!this.pending)
       return;
 
+    // For autofill entries, the comment field must be a stripped version
+    // of the final destination url, so that the user will definitely know
+    // where he is going to end up. For example, if the user is visiting a
+    // secure page, we'll leave the https on it, to let him know that.
+    // This must happen before generating the dedupe key.
+    if (match.hasOwnProperty("style") && match.style.includes("autofill")) {
+      // We fallback to match.value, as that's what autocomplete does if
+      // finalCompleteValue is null.
+      // Trim only if the value looks like a domain, we want to retain the
+      // trailing slash if we're completing a url to the next slash.
+      match.comment = stripHttpAndTrim(match.finalCompleteValue || match.value,
+                                       !this._searchString.includes("/"));
+    }
+
     // Must check both id and url, cause keywords dynamically modify the url.
     let urlMapKey = makeKeyForURL(match);
     if ((match.placeId && this._usedPlaceIds.has(match.placeId)) ||
         this._usedURLs.has(urlMapKey)) {
       return;
     }
 
     // Add this to our internal tracker to ensure duplicates do not end up in
@@ -1693,89 +1692,79 @@ Search.prototype = {
       }
       this._localMatchesCount++;
     }
     return index;
   },
 
   _processHostRow(row) {
     let match = {};
-    let trimmedHost = row.getResultByIndex(QUERYINDEX_URL);
-    let untrimmedHost = row.getResultByIndex(QUERYINDEX_TITLE);
+    let strippedHost = row.getResultByIndex(QUERYINDEX_URL);
+    let unstrippedHost = row.getResultByIndex(QUERYINDEX_TITLE);
     let frecency = row.getResultByIndex(QUERYINDEX_FRECENCY);
     let faviconUrl = row.getResultByIndex(QUERYINDEX_ICONURL);
 
-    // If the untrimmed value doesn't preserve the user's input just
+    // If the unfixup value doesn't preserve the user's input just
     // ignore it and complete to the found host.
-    if (untrimmedHost &&
-        !untrimmedHost.toLowerCase().includes(this._trimmedOriginalSearchString.toLowerCase())) {
-      untrimmedHost = null;
+    if (!unstrippedHost.toLowerCase().includes(this._trimmedOriginalSearchString.toLowerCase())) {
+      unstrippedHost = null;
     }
 
-    match.value = this._strippedPrefix + trimmedHost;
-    match.finalCompleteValue = untrimmedHost;
-
-    // The comment should be the user's final destination so that the user
-    // will definitely know where he is going to end up. For example, if the
-    // user is visiting a secure page, we'll leave the https on it, so that
-    // they know it'll be secure.
-    // We fallback to match.value, as that's what autocomplete does if
-    // finalCompleteValue is null.
-    match.comment = stripHttpAndTrim(match.finalCompleteValue || match.value);
+    match.value = this._strippedPrefix + strippedHost;
+    match.finalCompleteValue = unstrippedHost;
 
     if (faviconUrl) {
       match.icon = PlacesUtils.favicons
                               .getFaviconLinkForIcon(NetUtil.newURI(faviconUrl)).spec;
     }
     // Although this has a frecency, this query is executed before any other
     // queries that would result in frecency matches.
     match.frecency = frecency;
     match.style = "autofill";
     return match;
   },
 
   _processUrlRow(row) {
-    let match = {};
-    let value = row.getResultByIndex(QUERYINDEX_URL);
-    let url = fixupSearchText(value);
+    let url = row.getResultByIndex(QUERYINDEX_URL);
+    let strippedUrl = stripPrefix(url);
+    let prefix = url.substr(0, url.length - strippedUrl.length);
     let frecency = row.getResultByIndex(QUERYINDEX_FRECENCY);
     let faviconUrl = row.getResultByIndex(QUERYINDEX_ICONURL);
 
-    let prefix = value.slice(0, value.length - stripPrefix(value).length);
-
     // We must complete the URL up to the next separator (which is /, ? or #).
-    let separatorIndex = url.slice(this._searchString.length)
-                            .search(/[\/\?\#]/);
+    let searchString = stripPrefix(this._trimmedOriginalSearchString);
+    let separatorIndex = strippedUrl.slice(searchString.length)
+                                    .search(/[\/\?\#]/);
     if (separatorIndex != -1) {
-      separatorIndex += this._searchString.length;
-      if (url[separatorIndex] == "/") {
+      separatorIndex += searchString.length;
+      if (strippedUrl[separatorIndex] == "/") {
         separatorIndex++; // Include the "/" separator
       }
-      url = url.slice(0, separatorIndex);
+      strippedUrl = strippedUrl.slice(0, separatorIndex);
     }
 
-    // If the untrimmed value doesn't preserve the user's input just
-    // ignore it and complete to the found url.
-    let untrimmedURL = prefix + url;
-    if (untrimmedURL &&
-        !untrimmedURL.toLowerCase().includes(this._trimmedOriginalSearchString.toLowerCase())) {
-      untrimmedURL = null;
-     }
+    let match = {
+      value: this._strippedPrefix + strippedUrl,
+      // Although this has a frecency, this query is executed before any other
+      // queries that would result in frecency matches.
+      frecency,
+      style: "autofill"
+    };
 
-    match.value = this._strippedPrefix + url;
-    match.comment = url;
-    match.finalCompleteValue = untrimmedURL;
     if (faviconUrl) {
       match.icon = PlacesUtils.favicons
                               .getFaviconLinkForIcon(NetUtil.newURI(faviconUrl)).spec;
     }
-    // Although this has a frecency, this query is executed before any other
-    // queries that would result in frecency matches.
-    match.frecency = frecency;
-    match.style = "autofill";
+
+    // Complete to the found url only if its untrimmed value preserves the
+    // user's input.
+    if (url.toLowerCase().includes(this._trimmedOriginalSearchString.toLowerCase())) {
+      match.finalCompleteValue = prefix + strippedUrl;
+    }
+
     return match;
   },
 
   _processRow(row) {
     let match = {};
     match.placeId = row.getResultByIndex(QUERYINDEX_PLACEID);
     let escapedURL = row.getResultByIndex(QUERYINDEX_URL);
     let openPageCount = row.getResultByIndex(QUERYINDEX_SWITCHTAB) || 0;
@@ -2014,35 +2003,42 @@ Search.prototype = {
    *
    * @return an array consisting of the correctly optimized query to search the
    *         database with and an object containing the params to bound.
    */
   get _urlQuery() {
     // We expect this to be a full URL, not just a host. We want to extract the
     // host and use that as a guess for whether we'll get a result from a URL
     // query.
-    let slashIndex = this._autofillUrlSearchString.indexOf("/");
-    let revHost = this._autofillUrlSearchString.substring(0, slashIndex).toLowerCase()
-                      .split("").reverse().join("") + ".";
+    // The URIs in the database are fixed-up, so we can match on a lowercased
+    // host, but the path must be matched in a case sensitive way.
+    let pathIndex = this._trimmedOriginalSearchString.indexOf("/", this._strippedPrefix.length);
+    let revHost = this._trimmedOriginalSearchString
+                      .substring(this._strippedPrefix.length, pathIndex)
+                      .toLowerCase().split("").reverse().join("") + ".";
+    let searchString = stripPrefix(
+      this._trimmedOriginalSearchString.slice(0, pathIndex).toLowerCase() +
+      this._trimmedOriginalSearchString.slice(pathIndex)
+    );
 
     let typed = Prefs.autofillTyped || this.hasBehavior("typed");
     let bookmarked = this.hasBehavior("bookmark") && !this.hasBehavior("history");
 
     let query = [];
     if (bookmarked) {
       query.push(typed ? SQL_BOOKMARKED_TYPED_URL_QUERY
                        : SQL_BOOKMARKED_URL_QUERY);
     } else {
       query.push(typed ? SQL_TYPED_URL_QUERY
                        : SQL_URL_QUERY);
     }
 
     query.push({
       query_type: QUERYTYPE_AUTOFILL_URL,
-      searchString: this._autofillUrlSearchString,
+      searchString,
       revHost
     });
 
     return query;
   },
 
  /**
    * Notifies the listener about results.

--- a/toolkit/components/places/tests/unifiedcomplete/head_autocomplete.js
+++ b/toolkit/components/places/tests/unifiedcomplete/head_autocomplete.js
@@ -369,17 +369,17 @@ function makeSearchMatch(input, extra = 
     searchQuery: "searchQuery" in extra ? extra.searchQuery : input,
   };
   if ("alias" in extra) {
     // May be undefined, which is expected, but in that case make sure it's not
     // included in the params of the moz-action URL.
     params.alias = extra.alias;
   }
   let style = [ "action", "searchengine" ];
-  if (Array.isArray(extra.style)) {
+  if ("style" in extra && Array.isArray(extra.style)) {
     style.push(...extra.style);
   }
   if (extra.heuristic) {
     style.push("heuristic");
   }
   return {
     uri: makeActionURI("searchengine", params),
     title: params.engineName,

new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/unifiedcomplete/test_encoded_urls.js
@@ -0,0 +1,71 @@
+add_task(function* test_encoded() {
+  do_print("Searching for over encoded url should not break it");
+  yield PlacesTestUtils.addVisits({
+    uri: NetUtil.newURI("https://www.mozilla.com/search/top/?q=%25%32%35"),
+    title: "https://www.mozilla.com/search/top/?q=%25%32%35",
+    transition: TRANSITION_TYPED
+  });
+  yield check_autocomplete({
+    search: "https://www.mozilla.com/search/top/?q=%25%32%35",
+    matches: [ { uri: NetUtil.newURI("https://www.mozilla.com/search/top/?q=%25%32%35"),
+                 title: "https://www.mozilla.com/search/top/?q=%25%32%35",
+                 style: [ "autofill", "heuristic" ] }],
+    autofilled: "https://www.mozilla.com/search/top/?q=%25%32%35",
+    completed: "https://www.mozilla.com/search/top/?q=%25%32%35"
+  });
+  yield cleanup();
+});
+
+add_task(function* test_encoded_trimmed() {
+  do_print("Searching for over encoded url should not break it");
+  yield PlacesTestUtils.addVisits({
+    uri: NetUtil.newURI("https://www.mozilla.com/search/top/?q=%25%32%35"),
+    title: "https://www.mozilla.com/search/top/?q=%25%32%35",
+    transition: TRANSITION_TYPED
+  });
+  yield check_autocomplete({
+    search: "mozilla.com/search/top/?q=%25%32%35",
+    matches: [ { uri: NetUtil.newURI("https://www.mozilla.com/search/top/?q=%25%32%35"),
+                 title: "https://www.mozilla.com/search/top/?q=%25%32%35",
+                 style: [ "autofill", "heuristic" ] }],
+    autofilled: "mozilla.com/search/top/?q=%25%32%35",
+    completed: "https://www.mozilla.com/search/top/?q=%25%32%35"
+  });
+  yield cleanup();
+});
+
+add_task(function* test_encoded_partial() {
+  do_print("Searching for over encoded url should not break it");
+  yield PlacesTestUtils.addVisits({
+    uri: NetUtil.newURI("https://www.mozilla.com/search/top/?q=%25%32%35"),
+    title: "https://www.mozilla.com/search/top/?q=%25%32%35",
+    transition: TRANSITION_TYPED
+  });
+  yield check_autocomplete({
+    search: "https://www.mozilla.com/search/top/?q=%25",
+    matches: [ { uri: NetUtil.newURI("https://www.mozilla.com/search/top/?q=%25%32%35"),
+                 title: "https://www.mozilla.com/search/top/?q=%25%32%35",
+                 style: [ "autofill", "heuristic" ] }],
+    autofilled: "https://www.mozilla.com/search/top/?q=%25%32%35",
+    completed: "https://www.mozilla.com/search/top/?q=%25%32%35"
+  });
+  yield cleanup();
+});
+
+add_task(function* test_encoded_path() {
+  do_print("Searching for over encoded url should not break it");
+  yield PlacesTestUtils.addVisits({
+    uri: NetUtil.newURI("https://www.mozilla.com/%25%32%35/top/"),
+    title: "https://www.mozilla.com/%25%32%35/top/",
+    transition: TRANSITION_TYPED
+  });
+  yield check_autocomplete({
+    search: "https://www.mozilla.com/%25%32%35/t",
+    matches: [ { uri: NetUtil.newURI("https://www.mozilla.com/%25%32%35/top/"),
+                 title: "https://www.mozilla.com/%25%32%35/top/",
+                 style: [ "autofill", "heuristic" ] }],
+    autofilled: "https://www.mozilla.com/%25%32%35/top/",
+    completed: "https://www.mozilla.com/%25%32%35/top/"
+  });
+  yield cleanup();
+});

--- a/toolkit/components/places/tests/unifiedcomplete/xpcshell.ini
+++ b/toolkit/components/places/tests/unifiedcomplete/xpcshell.ini
@@ -17,16 +17,17 @@ support-files =
 [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]
 [test_enabled.js]
+[test_encoded_urls.js]
 [test_escape_self.js]
 [test_extension_matches.js]
 [test_ignore_protocol.js]
 [test_keyword_search.js]
 [test_keyword_search_actions.js]
 [test_keywords.js]
 [test_match_beginning.js]
 [test_multi_word_search.js]