--- a/toolkit/components/telemetry/TelemetryEnvironment.jsm
+++ b/toolkit/components/telemetry/TelemetryEnvironment.jsm
@@ -246,16 +246,17 @@ const PREF_E10S_COHORT = "e10s.rollout.c
 
 const COMPOSITOR_CREATED_TOPIC = "compositor:created";
 const COMPOSITOR_PROCESS_ABORTED_TOPIC = "compositor:process-aborted";
 const DISTRIBUTION_CUSTOMIZATION_COMPLETE_TOPIC = "distribution-customization-complete";
 const EXPERIMENTS_CHANGED_TOPIC = "experiments-changed";
 const GFX_FEATURES_READY_TOPIC = "gfx-features-ready";
 const SEARCH_ENGINE_MODIFIED_TOPIC = "browser-search-engine-modified";
 const SEARCH_SERVICE_TOPIC = "browser-search-service";
+const SESSIONSTORE_WINDOWS_RESTORED_TOPIC = "sessionstore-windows-restored";
 
 /**
  * Enforces the parameter to a boolean value.
  * @param aValue The input value.
  * @return {Boolean|Object} If aValue is a boolean or a number, returns its truthfulness
  *         value. Otherwise, return null.
  */
 function enforceBoolean(aValue) {
@@ -772,33 +773,34 @@ EnvironmentAddonBuilder.prototype = {
 
 function EnvironmentCache() {
   this._log = Log.repository.getLoggerWithMessagePrefix(
     LOGGER_NAME, "TelemetryEnvironment::");
   this._log.trace("constructor");
 
   this._shutdown = false;
   this._delayedInitFinished = false;
+  // Don't allow querying the search service too early to prevent
+  // impacting the startup performance.
+  this._canQuerySearch = false;
 
   // A map of listeners that will be called on environment changes.
   this._changeListeners = new Map();
 
   // A map of watched preferences which trigger an Environment change when
   // modified. Every entry contains a recording policy (RECORD_PREF_*).
   this._watchedPrefs = DEFAULT_ENVIRONMENT_PREFS;
 
   this._currentEnvironment = {
     build: this._getBuild(),
     partner: this._getPartner(),
     system: this._getSystem(),
   };
 
   this._updateSettings();
-  // Fill in the default search engine, if the search provider is already initialized.
-  this._updateSearchEngine();
   this._addObservers();
 
   // Build the remaining asynchronous parts of the environment. Don't register change listeners
   // until the initial environment has been built.
 
   let p = [];
   this._addonBuilder = new EnvironmentAddonBuilder(this);
   p = [ this._addonBuilder.init() ];
@@ -1003,25 +1005,27 @@ EnvironmentCache.prototype = {
       if (!("requiresRestart" in options) || !options.requiresRestart) {
         Preferences.ignore(pref, this._onPrefChanged, this);
       }
     }
   },
 
   _addObservers() {
     // Watch the search engine change and service topics.
+    Services.obs.addObserver(this, SESSIONSTORE_WINDOWS_RESTORED_TOPIC);
     Services.obs.addObserver(this, COMPOSITOR_CREATED_TOPIC);
     Services.obs.addObserver(this, COMPOSITOR_PROCESS_ABORTED_TOPIC);
     Services.obs.addObserver(this, DISTRIBUTION_CUSTOMIZATION_COMPLETE_TOPIC);
     Services.obs.addObserver(this, GFX_FEATURES_READY_TOPIC);
     Services.obs.addObserver(this, SEARCH_ENGINE_MODIFIED_TOPIC);
     Services.obs.addObserver(this, SEARCH_SERVICE_TOPIC);
   },
 
   _removeObservers() {
+    Services.obs.removeObserver(this, SESSIONSTORE_WINDOWS_RESTORED_TOPIC);
     Services.obs.removeObserver(this, COMPOSITOR_CREATED_TOPIC);
     Services.obs.removeObserver(this, COMPOSITOR_PROCESS_ABORTED_TOPIC);
     try {
       Services.obs.removeObserver(this, DISTRIBUTION_CUSTOMIZATION_COMPLETE_TOPIC);
     } catch (ex) {}
     Services.obs.removeObserver(this, GFX_FEATURES_READY_TOPIC);
     Services.obs.removeObserver(this, SEARCH_ENGINE_MODIFIED_TOPIC);
     Services.obs.removeObserver(this, SEARCH_SERVICE_TOPIC);
@@ -1037,16 +1041,17 @@ EnvironmentCache.prototype = {
         // Record the new default search choice and send the change notification.
         this._onSearchEngineChange();
         break;
       case SEARCH_SERVICE_TOPIC:
         if (aData != "init-complete") {
           return;
         }
         // Now that the search engine init is complete, record the default search choice.
+        this._canQuerySearch = true;
         this._updateSearchEngine();
         break;
       case GFX_FEATURES_READY_TOPIC:
       case COMPOSITOR_CREATED_TOPIC:
         // Full graphics information is not available until we have created at
         // least one off-main-thread-composited window. Thus we wait for the
         // first compositor to be created and then query nsIGfxInfo again.
         this._updateGraphicsFeatures();
@@ -1057,16 +1062,21 @@ EnvironmentCache.prototype = {
         this._onCompositorProcessAborted();
         break;
       case DISTRIBUTION_CUSTOMIZATION_COMPLETE_TOPIC:
         // Distribution customizations are applied after final-ui-startup. query
         // partner prefs again when they are ready.
         this._updatePartner();
         Services.obs.removeObserver(this, aTopic);
         break;
+      case SESSIONSTORE_WINDOWS_RESTORED_TOPIC:
+        // Make sure to initialize the search service once we've done restoring
+        // the windows, so that we don't risk loosing search data.
+        Services.search.init();
+        break;
     }
   },
 
   /**
    * Get the default search engine.
    * @return {String} Returns the search engine identifier, "NONE" if no default search
    *         engine is defined or "UNDEFINED" if no engine identifier or name can be found.
    */
@@ -1089,16 +1099,21 @@ EnvironmentCache.prototype = {
 
     return name;
   },
 
   /**
    * Update the default search engine value.
    */
   _updateSearchEngine() {
+    if (!this._canQuerySearch) {
+      this._log.trace("_updateSearchEngine - ignoring early call");
+      return;
+    }
+
     if (!Services.search) {
       // Just ignore cases where the search service is not implemented.
       return;
     }
 
     this._log.trace("_updateSearchEngine - isInitialized: " + Services.search.isInitialized);
     if (!Services.search.isInitialized) {
       return;

--- a/toolkit/components/telemetry/tests/unit/xpcshell.ini
+++ b/toolkit/components/telemetry/tests/unit/xpcshell.ini
@@ -58,16 +58,17 @@ tags = addons
 run-sequentially = Bug 1046307, test can fail intermittently when CPU load is high
 [test_TelemetrySend.js]
 [test_ChildHistograms.js]
 skip-if = os == "android" # Disabled due to crashes (see bug 1331366)
 tags = addons
 [test_ChildScalars.js]
 skip-if = os == "android" # Disabled due to crashes (see bug 1331366)
 [test_TelemetryReportingPolicy.js]
+skip-if = os == "android" # Disabled due to crashes (see bug 1367762)
 tags = addons
 [test_TelemetryScalars.js]
 [test_TelemetryTimestamps.js]
 skip-if = toolkit == 'android'
 [test_TelemetryCaptureStack.js]
 [test_TelemetryEvents.js]
 [test_ChildEvents.js]
 skip-if = os == "android" # Disabled due to crashes (see bug 1331366)