--- a/browser/extensions/formautofill/FormAutofillContent.jsm
+++ b/browser/extensions/formautofill/FormAutofillContent.jsm
@@ -85,49 +85,57 @@ AutofillProfileAutoCompleteSearch.protot
    *
    * @param {string} searchString the string to search for
    * @param {string} searchParam
    * @param {Object} previousResult a previous result to use for faster searchinig
    * @param {Object} listener the listener to notify when the search is complete
    */
   startSearch(searchString, searchParam, previousResult, listener) {
     this.log.debug("startSearch: for", searchString, "with input", formFillController.focusedInput);
+
+    this.forceStop = false;
+
+    let savedFieldNames = FormAutofillContent.savedFieldNames;
+
     let focusedInput = formFillController.focusedInput;
-    this.forceStop = false;
     let info = FormAutofillContent.getInputDetails(focusedInput);
+    let isAddressField = FormAutofillUtils.isAddressField(info.fieldName);
+    let handler = FormAutofillContent.getFormHandler(focusedInput);
+    let allFieldNames = handler.allFieldNames;
+    let filledRecordGUID = isAddressField ? handler.address.filledRecordGUID : handler.creditCards.filledRecordGUID;
 
-    if (!FormAutofillContent.savedFieldNames.has(info.fieldName) ||
-        FormAutofillContent.getFormHandler(focusedInput).address.filledRecordGUID) {
+    // Fallback to form-history if ...
+    //   - no profile can fill the currently-focused input.
+    //   - the current form has already been populated.
+    //   - (address only) less than 3 inputs are covered by all saved fields in the storage.
+    if (!savedFieldNames.has(info.fieldName) || filledRecordGUID || (isAddressField &&
+        allFieldNames.filter(field => savedFieldNames.has(field)).length < FormAutofillUtils.AUTOFILL_FIELDS_THRESHOLD)) {
       let formHistory = Cc["@mozilla.org/autocomplete/search;1?name=form-history"]
                           .createInstance(Ci.nsIAutoCompleteSearch);
       formHistory.startSearch(searchString, searchParam, previousResult, {
         onSearchResult: (search, result) => {
           listener.onSearchResult(this, result);
           ProfileAutocomplete.setProfileAutoCompleteResult(result);
         },
       });
       return;
     }
 
-    let collectionName = FormAutofillUtils.isAddressField(info.fieldName) ?
-      "addresses" : "creditCards";
+    let collectionName = isAddressField ? "addresses" : "creditCards";
 
     this._getRecords({collectionName, info, searchString}).then((records) => {
       if (this.forceStop) {
         return;
       }
       // Sort addresses by timeLastUsed for showing the lastest used address at top.
       records.sort((a, b) => b.timeLastUsed - a.timeLastUsed);
 
-      let handler = FormAutofillContent.getFormHandler(focusedInput);
       let adaptedRecords = handler.getAdaptedProfiles(records);
-
-      let allFieldNames = FormAutofillContent.getAllFieldNames(focusedInput);
       let result = null;
-      if (collectionName == "addresses") {
+      if (isAddressField) {
         result = new AddressResult(searchString,
                                    info.fieldName,
                                    allFieldNames,
                                    adaptedRecords,
                                    {});
       } else {
         result = new CreditCardResult(searchString,
                                       info.fieldName,

--- a/browser/extensions/formautofill/test/mochitest/formautofill_common.js
+++ b/browser/extensions/formautofill/test/mochitest/formautofill_common.js
@@ -56,17 +56,18 @@ function checkMenuEntries(expectedValues
 }
 
 async function addAddress(address) {
   return new Promise(resolve => {
     formFillChromeScript.sendAsyncMessage("FormAutofillTest:AddAddress", {address});
     formFillChromeScript.addMessageListener("FormAutofillTest:AddressAdded", function onAdded(data) {
       formFillChromeScript.removeMessageListener("FormAutofillTest:AddressAdded", onAdded);
 
-      resolve();
+      SimpleTest.requestFlakyTimeout("Ensure ProfileAutocomplete is registered");
+      setTimeout(resolve, 500);
     });
   });
 }
 
 async function removeAddress(guid) {
   return new Promise(resolve => {
     formFillChromeScript.sendAsyncMessage("FormAutofillTest:RemoveAddress", {guid});
     formFillChromeScript.addMessageListener("FormAutofillTest:AddressRemoved", function onDeleted(data) {
@@ -94,16 +95,27 @@ async function checkAddresses(expectedAd
     formFillChromeScript.addMessageListener("FormAutofillTest:areAddressesMatching", function onChecked(data) {
       formFillChromeScript.removeMessageListener("FormAutofillTest:areAddressesMatching", onChecked);
 
       resolve(data);
     });
   });
 }
 
+async function cleanUpAddress() {
+  return new Promise(resolve => {
+    formFillChromeScript.sendAsyncMessage("FormAutofillTest:CleanUpAddress", {});
+    formFillChromeScript.addMessageListener("FormAutofillTest:AddressCleanedUp", function onCleanedUp(data) {
+      formFillChromeScript.removeMessageListener("FormAutofillTest:AddressCleanedUp", onCleanedUp);
+
+      resolve(data);
+    });
+  });
+}
+
 // Utils for registerPopupShownListener(in satchel_common.js) that handles dropdown popup
 // Please call "initPopupListener()" in your test and "await expectPopup()"
 // if you want to wait for dropdown menu displayed.
 function expectPopup() {
   info("expecting a popup");
   return new Promise(resolve => {
     expectingPopup = resolve;
   });

--- a/browser/extensions/formautofill/test/mochitest/formautofill_parent_utils.js
+++ b/browser/extensions/formautofill/test/mochitest/formautofill_parent_utils.js
@@ -12,16 +12,24 @@ let {profileStorage} = Cu.import("resour
 var ParentUtils = {
   cleanUpAddress() {
     Services.cpmm.addMessageListener("FormAutofill:Records", function getResult(result) {
       Services.cpmm.removeMessageListener("FormAutofill:Records", getResult);
 
       let addresses = result.data;
       Services.cpmm.sendAsyncMessage("FormAutofill:RemoveAddresses",
                                      {guids: addresses.map(address => address.guid)});
+
+      let count = addresses.length;
+      Services.obs.addObserver(function observer(subject, topic, data) {
+        if (!--count) {
+          Services.obs.removeObserver(observer, topic);
+          sendAsyncMessage("FormAutofillTest:AddressCleanedUp");
+        }
+      }, "formautofill-storage-changed");
     });
 
     Services.cpmm.sendAsyncMessage("FormAutofill:GetRecords", {searchString: "", collectionName: "addresses"});
   },
 
   updateAddress(type, chromeMsg, msgData, contentMsg) {
     Services.cpmm.sendAsyncMessage(chromeMsg, msgData);
     Services.obs.addObserver(function observer(subject, topic, data) {
@@ -99,11 +107,15 @@ addMessageListener("FormAutofillTest:Rem
 addMessageListener("FormAutofillTest:UpdateAddress", (msg) => {
   ParentUtils.updateAddress("update", "FormAutofill:SaveAddress", msg, "FormAutofillTest:AddressUpdated");
 });
 
 addMessageListener("FormAutofillTest:CheckAddresses", (msg) => {
   ParentUtils.checkAddresses(msg);
 });
 
+addMessageListener("FormAutofillTest:CleanUpAddress", (msg) => {
+  ParentUtils.cleanUpAddress();
+});
+
 addMessageListener("cleanup", () => {
   ParentUtils.cleanup();
 });

--- a/browser/extensions/formautofill/test/mochitest/test_basic_autocomplete_form.html
+++ b/browser/extensions/formautofill/test/mochitest/test_basic_autocomplete_form.html
@@ -99,16 +99,31 @@ add_task(async function history_only_men
   await setupFormHistory();
 
   await setInput("#tel", "");
   doKey("down");
   await expectPopup();
   checkMenuEntries(["+1234567890"], false);
 });
 
+// Display history search result if less than 3 inputs are covered by all saved
+// fields in the storage.
+add_task(async function all_saved_fields_less_than_threshold() {
+  await addAddress({
+    email: "test@test.com",
+  });
+
+  await setInput("#email", "");
+  doKey("down");
+  await expectPopup();
+  checkMenuEntries(["foo@mozilla.com"], false);
+
+  await cleanUpAddress();
+});
+
 // Form with both history and address storage.
 add_task(async function check_menu_when_both_existed() {
   await setupAddressStorage();
 
   await setInput("#organization", "");
   doKey("down");
   await expectPopup();
   checkMenuEntries(MOCK_STORAGE.map(address =>