--- a/mobile/android/base/java/org/mozilla/gecko/GeckoApp.java
+++ b/mobile/android/base/java/org/mozilla/gecko/GeckoApp.java
@@ -72,16 +72,17 @@ import android.os.Build;
 import android.os.Bundle;
 import android.os.Environment;
 import android.os.Handler;
 import android.os.PowerManager;
 import android.os.Process;
 import android.os.StrictMode;
 import android.provider.ContactsContract;
 import android.provider.MediaStore.Images.Media;
+import android.support.annotation.WorkerThread;
 import android.support.design.widget.Snackbar;
 import android.text.TextUtils;
 import android.util.AttributeSet;
 import android.util.Base64;
 import android.util.Log;
 import android.util.SparseBooleanArray;
 import android.view.Gravity;
 import android.view.KeyEvent;
@@ -196,16 +197,18 @@ public abstract class GeckoApp
 
     private FullScreenHolder mFullScreenPluginContainer;
     private View mFullScreenPluginView;
 
     private final HashMap<String, PowerManager.WakeLock> mWakeLocks = new HashMap<String, PowerManager.WakeLock>();
 
     protected boolean mLastSessionCrashed;
     protected boolean mShouldRestore;
+    private boolean mSessionRestoreParsingFinished = false;
+
     protected boolean mInitialized;
     protected boolean mWindowFocusInitialized;
     private Telemetry.Timer mJavaUiStartupTimer;
     private Telemetry.Timer mGeckoReadyStartupTimer;
 
     private String mPrivateBrowsingSession;
 
     private volatile HealthRecorder mHealthRecorder;
@@ -1271,16 +1274,53 @@ public abstract class GeckoApp
             // from "Don't keep activities" on ICS)
             if (!wasInBackground && !mIsRestoringActivity) {
                 Telemetry.addToHistogram("FENNEC_WAS_KILLED", 1);
             }
 
             mPrivateBrowsingSession = savedInstanceState.getString(SAVED_STATE_PRIVATE_SESSION);
         }
 
+        ThreadUtils.postToBackgroundThread(new Runnable() {
+            @Override
+            public void run() {
+                // If we are doing a restore, read the session data so we can send it to Gecko later.
+                String restoreMessage = null;
+                if (!mIsRestoringActivity && mShouldRestore) {
+                    try {
+                        // restoreSessionTabs() will create simple tab stubs with the
+                        // URL and title for each page, but we also need to restore
+                        // session history. restoreSessionTabs() will inject the IDs
+                        // of the tab stubs into the JSON data (which holds the session
+                        // history). This JSON data is then sent to Gecko so session
+                        // history can be restored for each tab.
+                        final SafeIntent intent = new SafeIntent(getIntent());
+                        restoreMessage = restoreSessionTabs(invokedWithExternalURL(getIntentURI(intent)));
+                    } catch (SessionRestoreException e) {
+                        // If restore failed, do a normal startup
+                        Log.e(LOGTAG, "An error occurred during restore", e);
+                        mShouldRestore = false;
+                    }
+                }
+
+                synchronized (this) {
+                    mSessionRestoreParsingFinished = true;
+                    notifyAll();
+                }
+
+                // If we are doing a restore, send the parsed session data to Gecko.
+                if (!mIsRestoringActivity) {
+                    GeckoAppShell.notifyObservers("Session:Restore", restoreMessage);
+                }
+
+                // Make sure sessionstore.bak is either updated or deleted as necessary.
+                getProfile().updateSessionFile(mShouldRestore);
+            }
+        });
+
         // Perform background initialization.
         ThreadUtils.postToBackgroundThread(new Runnable() {
             @Override
             public void run() {
                 final SharedPreferences prefs = GeckoApp.this.getSharedPreferences();
 
                 // Wait until now to set this, because we'd rather throw an exception than
                 // have a caller of BrowserLocaleManager regress startup.
@@ -1484,36 +1524,27 @@ public abstract class GeckoApp
         // Start migrating as early as possible, can do this in
         // parallel with Gecko load.
         checkMigrateProfile();
 
         Tabs.registerOnTabsChangedListener(this);
 
         initializeChrome();
 
-        // If we are doing a restore, read the session data and send it to Gecko
-        if (!mIsRestoringActivity) {
-            String restoreMessage = null;
-            if (mShouldRestore) {
+        // We need to wait here because mShouldRestore can revert back to
+        // false if a parsing error occurs and the startup tab we load
+        // depends on whether we restore tabs or not.
+        synchronized (this) {
+            while (!mSessionRestoreParsingFinished) {
                 try {
-                    // restoreSessionTabs() will create simple tab stubs with the
-                    // URL and title for each page, but we also need to restore
-                    // session history. restoreSessionTabs() will inject the IDs
-                    // of the tab stubs into the JSON data (which holds the session
-                    // history). This JSON data is then sent to Gecko so session
-                    // history can be restored for each tab.
-                    restoreMessage = restoreSessionTabs(isExternalURL);
-                } catch (SessionRestoreException e) {
-                    // If restore failed, do a normal startup
-                    Log.e(LOGTAG, "An error occurred during restore", e);
-                    mShouldRestore = false;
+                    wait();
+                } catch (final InterruptedException e) {
+                    // Ignore and wait again.
                 }
             }
-
-            GeckoAppShell.notifyObservers("Session:Restore", restoreMessage);
         }
 
         // External URLs should always be loaded regardless of whether Gecko is
         // already running.
         if (isExternalURL) {
             // Restore tabs before opening an external URL so that the new tab
             // is animated properly.
             Tabs.getInstance().notifyListeners(null, Tabs.TabEvents.RESTORED);
@@ -1535,19 +1566,16 @@ public abstract class GeckoApp
                 loadStartupTab(Tabs.LOADURL_NEW_TAB);
             }
 
             Tabs.getInstance().notifyListeners(null, Tabs.TabEvents.RESTORED);
 
             processTabQueue();
         }
 
-        // Make sure sessionstore.bak is either updated or deleted as necessary.
-        getProfile().updateSessionFile(mShouldRestore);
-
         recordStartupActionTelemetry(passedUri, action);
 
         // Check if launched from data reporting notification.
         if (ACTION_LAUNCH_SETTINGS.equals(action)) {
             Intent settingsIntent = new Intent(GeckoApp.this, GeckoPreferences.class);
             // Copy extras.
             settingsIntent.putExtras(intent.getUnsafe());
             startActivity(settingsIntent);
@@ -1646,41 +1674,47 @@ public abstract class GeckoApp
                     TabQueueHelper.openQueuedUrls(GeckoApp.this, getProfile(), TabQueueHelper.FILE_NAME, true);
                 } else {
                     openTabsRunnable.run();
                 }
             }
         });
     }
 
+    @WorkerThread
     private String restoreSessionTabs(final boolean isExternalURL) throws SessionRestoreException {
         try {
             String sessionString = getProfile().readSessionFile(false);
             if (sessionString == null) {
                 throw new SessionRestoreException("Could not read from session file");
             }
 
             // If we are doing an OOM restore, parse the session data and
             // stub the restored tabs immediately. This allows the UI to be
             // updated before Gecko has restored.
             if (mShouldRestore) {
                 final JSONArray tabs = new JSONArray();
                 final JSONObject windowObject = new JSONObject();
                 SessionParser parser = new SessionParser() {
                     @Override
-                    public void onTabRead(SessionTab sessionTab) {
+                    public void onTabRead(final SessionTab sessionTab) {
                         JSONObject tabObject = sessionTab.getTabObject();
 
                         int flags = Tabs.LOADURL_NEW_TAB;
                         flags |= ((isExternalURL || !sessionTab.isSelected()) ? Tabs.LOADURL_DELAY_LOAD : 0);
                         flags |= (tabObject.optBoolean("desktopMode") ? Tabs.LOADURL_DESKTOP : 0);
                         flags |= (tabObject.optBoolean("isPrivate") ? Tabs.LOADURL_PRIVATE : 0);
 
-                        Tab tab = Tabs.getInstance().loadUrl(sessionTab.getUrl(), flags);
-                        tab.updateTitle(sessionTab.getTitle());
+                        final Tab tab = Tabs.getInstance().loadUrl(sessionTab.getUrl(), flags);
+                        ThreadUtils.postToUiThread(new Runnable() {
+                            @Override
+                            public void run() {
+                                tab.updateTitle(sessionTab.getTitle());
+                            }
+                        });
 
                         try {
                             tabObject.put("tabId", tab.getId());
                         } catch (JSONException e) {
                             Log.e(LOGTAG, "JSON error", e);
                         }
                         tabs.put(tabObject);
                     }

--- a/mobile/android/base/java/org/mozilla/gecko/GeckoProfile.java
+++ b/mobile/android/base/java/org/mozilla/gecko/GeckoProfile.java
@@ -72,16 +72,18 @@ public final class GeckoProfile {
     public static final String CUSTOM_PROFILE = "";
     public static final String GUEST_PROFILE_DIR = "guest";
 
     // Session store
     private static final String SESSION_FILE = "sessionstore.js";
     private static final String SESSION_FILE_BACKUP = "sessionstore.bak";
     private static final long MAX_BACKUP_FILE_AGE = 1000 * 3600 * 24; // 24 hours
 
+    private boolean mOldSessionDataProcessed = false;
+
     private static final HashMap<String, GeckoProfile> sProfileCache = new HashMap<String, GeckoProfile>();
     private static String sDefaultProfileName;
 
     private final String mName;
     private final File mMozillaDir;
     private final Context mApplicationContext;
 
     private final BrowserDB mDB;
@@ -596,16 +598,32 @@ public final class GeckoProfile {
                 sessionFile.renameTo(sessionFileBackup);
             }
         } else {
             if (sessionFileBackup != null && sessionFileBackup.exists() &&
                     System.currentTimeMillis() - sessionFileBackup.lastModified() > MAX_BACKUP_FILE_AGE) {
                 sessionFileBackup.delete();
             }
         }
+        synchronized (this) {
+            mOldSessionDataProcessed = true;
+            notifyAll();
+        }
+    }
+
+    public void waitForOldSessionDataProcessing() {
+        synchronized (this) {
+            while (!mOldSessionDataProcessed) {
+                try {
+                    wait();
+                } catch (final InterruptedException e) {
+                    // Ignore and wait again.
+                }
+            }
+        }
     }
 
     /**
      * Get the string from a session file.
      *
      * The session can either be read from sessionstore.js or sessionstore.bak.
      * In general, sessionstore.js holds the current session, and
      * sessionstore.bak holds the previous session.

--- a/mobile/android/base/java/org/mozilla/gecko/home/RecentTabsPanel.java
+++ b/mobile/android/base/java/org/mozilla/gecko/home/RecentTabsPanel.java
@@ -324,16 +324,19 @@ public class RecentTabsPanel extends Hom
                 }
 
                 // Add an "Open all" button if more than 2 tabs were added to the list.
                 if (visibleClosedTabs > 1) {
                     addRow(c, null, null, RecentTabs.TYPE_OPEN_ALL_CLOSED, null);
                 }
             }
 
+            // We need to ensure that the session restore code has updated sessionstore.bak as necessary.
+            GeckoProfile.get(context).waitForOldSessionDataProcessing();
+
             final String jsonString = GeckoProfile.get(context).readSessionFile(true);
             if (jsonString == null) {
                 // No previous session data
                 return c;
             }
 
             final int count = c.getCount();