--- a/mobile/android/base/GeckoApp.java
+++ b/mobile/android/base/GeckoApp.java
@@ -1905,16 +1905,17 @@ public abstract class GeckoApp
                 SharedPreferences.Editor editor = prefs.edit();
                 editor.putBoolean(GeckoApp.PREFS_WAS_STOPPED, false);
                 currentSession.recordBegin(editor);
                 editor.apply();
 
                 final HealthRecorder rec = mHealthRecorder;
                 if (rec != null) {
                     rec.setCurrentSession(currentSession);
+                    rec.processDelayed();
                 } else {
                     Log.w(LOGTAG, "Can't record session: rec is null.");
                 }
             }
          });
     }
 
     @Override

--- a/mobile/android/base/health/BrowserHealthRecorder.java
+++ b/mobile/android/base/health/BrowserHealthRecorder.java
@@ -12,16 +12,17 @@ import java.nio.charset.Charset;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Scanner;
 import java.util.Set;
+import java.util.concurrent.ConcurrentLinkedQueue;
 import java.util.concurrent.atomic.AtomicBoolean;
 
 import org.json.JSONException;
 import org.json.JSONObject;
 import org.mozilla.gecko.AppConstants;
 import org.mozilla.gecko.EventDispatcher;
 import org.mozilla.gecko.GeckoAppShell;
 import org.mozilla.gecko.GeckoEvent;
@@ -894,9 +895,47 @@ public class BrowserHealthRecorder imple
             // Continue so we don't hit it next time.
             // Future: record this exception in FHR's own error submitter.
         }
 
         // Track the end of this session in shared prefs, so it doesn't get
         // double-counted on next run.
         session.recordCompletion(editor);
     }
+
+    private static class Search {
+        public final String location;
+        public final String engineID;
+
+        public Search(final String location, final String engineID) {
+            if (!SEARCH_LOCATIONS.contains(location)) {
+                throw new IllegalArgumentException("Unknown search location: " + location);
+            }
+
+            this.location = location;
+            this.engineID = engineID;
+        }
+    }
+
+    private static ConcurrentLinkedQueue<Search> delayedSearches = new ConcurrentLinkedQueue<>();
+
+    public static void recordSearchDelayed(String location, String engineID) {
+        final Search search = new Search(location, engineID);
+        delayedSearches.add(search);
+    }
+
+    @Override
+    public void processDelayed() {
+        if (delayedSearches.isEmpty()) {
+            return;
+        }
+
+        if (this.state != State.INITIALIZED) {
+            Log.d(LOG_TAG, "Not initialized: not processing delayed items. (" + this.state + ")");
+            return;
+        }
+
+        Search poll;
+        while ((poll = delayedSearches.poll()) != null) {
+            recordSearch(poll.engineID, poll.location);
+        }
+    }
 }

--- a/mobile/android/base/health/HealthRecorder.java
+++ b/mobile/android/base/health/HealthRecorder.java
@@ -29,9 +29,11 @@ public interface HealthRecorder {
 
     public void onAppLocaleChanged(String to);
     public void onAddonChanged(String id, JSONObject json);
     public void onAddonUninstalling(String id);
     public void onEnvironmentChanged();
     public void onEnvironmentChanged(final boolean startNewSession, final String sessionEndReason);
 
     public void close();
+
+    public void processDelayed();
 }

--- a/mobile/android/base/health/StubbedHealthRecorder.java
+++ b/mobile/android/base/health/StubbedHealthRecorder.java
@@ -27,9 +27,12 @@ public class StubbedHealthRecorder imple
 
     public void onAppLocaleChanged(String to) { }
     public void onAddonChanged(String id, JSONObject json) { }
     public void onAddonUninstalling(String id) { }
     public void onEnvironmentChanged() { }
     public void onEnvironmentChanged(final boolean startNewSession, final String sessionEndReason) { }
 
     public void close() { }
+
+    @Override
+    public void processDelayed() { }
 }