--- a/mobile/android/base/android-services.mozbuild
+++ b/mobile/android/base/android-services.mozbuild
@@ -1036,16 +1036,17 @@ sync_java_files = [TOPSRCDIR + '/mobile/
     'sync/setup/activities/WebURLFinder.java',
     'sync/setup/Constants.java',
     'sync/setup/InvalidSyncKeyException.java',
     'sync/SharedPreferencesClientsDataDelegate.java',
     'sync/stage/AbstractNonRepositorySyncStage.java',
     'sync/stage/AbstractSessionManagingSyncStage.java',
     'sync/stage/AndroidBrowserBookmarksServerSyncStage.java',
     'sync/stage/AndroidBrowserHistoryServerSyncStage.java',
+    'sync/stage/AndroidBrowserRecentHistoryServerSyncStage.java',
     'sync/stage/CheckPreconditionsStage.java',
     'sync/stage/CompletedStage.java',
     'sync/stage/EnsureCrypto5KeysStage.java',
     'sync/stage/FennecTabsServerSyncStage.java',
     'sync/stage/FetchInfoCollectionsStage.java',
     'sync/stage/FetchInfoConfigurationStage.java',
     'sync/stage/FetchMetaGlobalStage.java',
     'sync/stage/FormHistoryServerSyncStage.java',

--- a/mobile/android/services/src/main/java/org/mozilla/gecko/sync/GlobalSession.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/sync/GlobalSession.java
@@ -22,16 +22,17 @@ import org.mozilla.gecko.sync.net.BaseRe
 import org.mozilla.gecko.sync.net.HttpResponseObserver;
 import org.mozilla.gecko.sync.net.SyncResponse;
 import org.mozilla.gecko.sync.net.SyncStorageRecordRequest;
 import org.mozilla.gecko.sync.net.SyncStorageRequest;
 import org.mozilla.gecko.sync.net.SyncStorageRequestDelegate;
 import org.mozilla.gecko.sync.net.SyncStorageResponse;
 import org.mozilla.gecko.sync.stage.AndroidBrowserBookmarksServerSyncStage;
 import org.mozilla.gecko.sync.stage.AndroidBrowserHistoryServerSyncStage;
+import org.mozilla.gecko.sync.stage.AndroidBrowserRecentHistoryServerSyncStage;
 import org.mozilla.gecko.sync.stage.CheckPreconditionsStage;
 import org.mozilla.gecko.sync.stage.CompletedStage;
 import org.mozilla.gecko.sync.stage.EnsureCrypto5KeysStage;
 import org.mozilla.gecko.sync.stage.FennecTabsServerSyncStage;
 import org.mozilla.gecko.sync.stage.FetchInfoCollectionsStage;
 import org.mozilla.gecko.sync.stage.FetchInfoConfigurationStage;
 import org.mozilla.gecko.sync.stage.FetchMetaGlobalStage;
 import org.mozilla.gecko.sync.stage.FormHistoryServerSyncStage;
@@ -183,19 +184,24 @@ public class GlobalSession implements Ht
     stages.put(Stage.fetchInfoConfiguration,  new FetchInfoConfigurationStage(
             config.infoConfigurationURL(), getAuthHeaderProvider()));
     stages.put(Stage.ensureKeysStage,         new EnsureCrypto5KeysStage());
 
     stages.put(Stage.syncClientsEngine,       new SyncClientsEngineStage());
 
     stages.put(Stage.syncTabs,                new FennecTabsServerSyncStage());
     stages.put(Stage.syncPasswords,           new PasswordsServerSyncStage());
+
+    // Will only run if syncFullHistory stage never completed.
+    // Bug 1316110 tracks follow up work to improve efficiency of this stage.
+    stages.put(Stage.syncRecentHistory,       new AndroidBrowserRecentHistoryServerSyncStage());
+
     stages.put(Stage.syncBookmarks,           new AndroidBrowserBookmarksServerSyncStage());
-    stages.put(Stage.syncHistory,             new AndroidBrowserHistoryServerSyncStage());
     stages.put(Stage.syncFormHistory,         new FormHistoryServerSyncStage());
+    stages.put(Stage.syncFullHistory,         new AndroidBrowserHistoryServerSyncStage());
 
     stages.put(Stage.uploadMetaGlobal,        new UploadMetaGlobalStage());
     stages.put(Stage.completed,               new CompletedStage());
 
     this.stages = Collections.unmodifiableMap(stages);
   }
 
   public GlobalSyncStage getSyncStageByName(String name) throws NoSuchStageException {

new file mode 100644
--- /dev/null
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/sync/stage/AndroidBrowserRecentHistoryServerSyncStage.java
@@ -0,0 +1,88 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+package org.mozilla.gecko.sync.stage;
+
+import org.mozilla.gecko.sync.MetaGlobalException;
+import org.mozilla.gecko.sync.NonObjectJSONException;
+import org.mozilla.gecko.sync.SynchronizerConfiguration;
+import org.mozilla.gecko.sync.middleware.BufferingMiddlewareRepository;
+import org.mozilla.gecko.sync.middleware.storage.MemoryBufferStorage;
+import org.mozilla.gecko.sync.repositories.ConstrainedServer11Repository;
+import org.mozilla.gecko.sync.repositories.Repository;
+import org.mozilla.gecko.sync.repositories.android.AndroidBrowserHistoryRepository;
+
+import java.io.IOException;
+import java.net.URISyntaxException;
+
+/**
+ * History sync stage which is limited to just recent history, and will only run if the full history
+ * sync stage did not complete yet. Its purpose is to give users with a lot of history in their
+ * profiles a good experience during a large collection sync.
+ *
+ * @author grisha
+ */
+public class AndroidBrowserRecentHistoryServerSyncStage extends AndroidBrowserHistoryServerSyncStage {
+    protected static final String LOG_TAG = "RecentHistoryStage";
+
+    // TODO: Bug 1316110 tracks follow up work to make this stage more efficient.
+    private static final int HISTORY_BATCH_LIMIT = 50;
+    // We need a custom configuration bundle name for this stage, because we want to track last-synced
+    // timestamp for this stage separately from that of a full history sync stage, yet their collection
+    // names are the same.
+    private static final String BUNDLE_NAME = "recentHistory.";
+    private static final String HISTORY_SORT = "newest";
+
+    @Override
+    public String bundlePrefix() {
+        return BUNDLE_NAME;
+    }
+
+    @Override
+    protected Repository getLocalRepository() {
+        return new BufferingMiddlewareRepository(
+                session.getSyncDeadline(),
+                new MemoryBufferStorage(),
+                new AndroidBrowserHistoryRepository()
+        );
+    }
+
+    @Override
+    protected Repository getRemoteRepository() throws URISyntaxException {
+        return new ConstrainedServer11Repository(
+                getCollection(),
+                session.getSyncDeadline(),
+                session.config.storageURL(),
+                session.getAuthHeaderProvider(),
+                session.config.infoCollections,
+                session.config.infoConfiguration,
+                HISTORY_BATCH_LIMIT,
+                HISTORY_SORT,
+                false /* force single batch only */);
+    }
+
+    /**
+     * This stage is only enabled if full history session is enabled and did not complete a sync yet.
+     */
+    @Override
+    public boolean isEnabled() throws MetaGlobalException {
+        final boolean historyStageEnabled = super.isEnabled();
+        if (!historyStageEnabled) {
+            return false;
+        }
+
+        if (session.config == null) {
+            return false;
+        }
+
+        final SynchronizerConfiguration synchronizerConfiguration;
+        try {
+            synchronizerConfiguration = new SynchronizerConfiguration(session.config.getBranch(getCollection() + "."));
+        } catch (IOException|NonObjectJSONException e) {
+            return false;
+        }
+
+        return synchronizerConfiguration.localBundle.getTimestamp() == -1;
+    }
+}

--- a/mobile/android/services/src/main/java/org/mozilla/gecko/sync/stage/GlobalSyncStage.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/sync/stage/GlobalSyncStage.java
@@ -28,18 +28,19 @@ public interface GlobalSyncStage {
     syncClientsEngine(SyncClientsEngineStage.STAGE_NAME),
     /*
     processFirstSyncPref,
     processClientCommands,
     updateEnabledEngines,
     */
     syncTabs("tabs"),
     syncPasswords("passwords"),
+    syncRecentHistory("recentHistory"),
     syncBookmarks("bookmarks"),
-    syncHistory("history"),
+    syncFullHistory("history"),
     syncFormHistory("forms"),
 
     uploadMetaGlobal,
     completed;
 
     // Maintain a mapping from names ("bookmarks") to Stage enumerations (syncBookmarks).
     private static final Map<String, Stage> named = new HashMap<String, Stage>();
     static {

--- a/mobile/android/tests/background/junit4/src/org/mozilla/android/sync/net/test/TestGlobalSession.java
+++ b/mobile/android/tests/background/junit4/src/org/mozilla/android/sync/net/test/TestGlobalSession.java
@@ -344,17 +344,17 @@ public class TestGlobalSession {
     MetaGlobal mg = session.generateNewMetaGlobal();
     assertEquals(Long.valueOf(GlobalSession.STORAGE_VERSION), mg.getStorageVersion());
     assertEquals(VersionConstants.BOOKMARKS_ENGINE_VERSION, mg.getEngines().getObject("bookmarks").getIntegerSafely("version").intValue());
     assertEquals(VersionConstants.CLIENTS_ENGINE_VERSION, mg.getEngines().getObject("clients").getIntegerSafely("version").intValue());
 
     List<String> namesList = new ArrayList<String>(mg.getEnabledEngineNames());
     Collections.sort(namesList);
     String[] names = namesList.toArray(new String[namesList.size()]);
-    String[] expected = new String[] { "bookmarks", "clients", "forms", "history", "passwords", "tabs" };
+    String[] expected = new String[] { "bookmarks", "clients", "forms", "history", "passwords", "recentHistory", "tabs" };
     assertArrayEquals(expected, names);
   }
 
   @Test
   public void testGenerateNewMetaGlobalSomePersisted() throws Exception {
     final MockGlobalSessionCallback callback = new MockGlobalSessionCallback();
     final GlobalSession session = MockPrefsGlobalSession.getSession(TEST_USERNAME, TEST_PASSWORD,
         new KeyBundle(TEST_USERNAME, TEST_SYNC_KEY), callback, null, null);

--- a/mobile/android/tests/background/junit4/src/org/mozilla/android/sync/test/TestResetCommands.java
+++ b/mobile/android/tests/background/junit4/src/org/mozilla/android/sync/test/TestResetCommands.java
@@ -112,17 +112,17 @@ public class TestResetCommands {
     final MockServerSyncStage stageNotReset = new MockServerSyncStage() {
       @Override
       public void resetLocal() {
         no.called = true;
       }
     };
 
     stagesToRun.put(Stage.syncBookmarks, stageGetsReset);
-    stagesToRun.put(Stage.syncHistory,   stageNotReset);
+    stagesToRun.put(Stage.syncFullHistory, stageNotReset);
 
     final String resetBookmarks = "{\"args\":[\"bookmarks\"],\"command\":\"resetEngine\"}";
     ExtendedJSONObject unparsedCommand = new ExtendedJSONObject(resetBookmarks);
     CommandProcessor processor = CommandProcessor.getProcessor();
     processor.processCommand(session, unparsedCommand);
 
     assertTrue(yes.called);
     assertFalse(no.called);

--- a/mobile/android/tests/background/junit4/src/org/mozilla/gecko/sync/stage/test/TestStageLookup.java
+++ b/mobile/android/tests/background/junit4/src/org/mozilla/gecko/sync/stage/test/TestStageLookup.java
@@ -19,23 +19,25 @@ public class TestStageLookup {
   @Test
   public void testStageLookupByName() {
     Set<Stage> namedStages = new HashSet<Stage>(Stage.getNamedStages());
     Set<Stage> expected = new HashSet<Stage>();
     expected.add(Stage.syncClientsEngine);
     expected.add(Stage.syncBookmarks);
     expected.add(Stage.syncTabs);
     expected.add(Stage.syncFormHistory);
-    expected.add(Stage.syncHistory);
+    expected.add(Stage.syncFullHistory);
+    expected.add(Stage.syncRecentHistory);
     expected.add(Stage.syncPasswords);
 
     assertEquals(expected, namedStages);
     assertEquals(Stage.syncClientsEngine, Stage.byName("clients"));
     assertEquals(Stage.syncTabs,          Stage.byName("tabs"));
     assertEquals(Stage.syncBookmarks,     Stage.byName("bookmarks"));
     assertEquals(Stage.syncFormHistory,   Stage.byName("forms"));
-    assertEquals(Stage.syncHistory,       Stage.byName("history"));
+    assertEquals(Stage.syncFullHistory,   Stage.byName("history"));
+    assertEquals(Stage.syncRecentHistory, Stage.byName("recentHistory"));
     assertEquals(Stage.syncPasswords,     Stage.byName("passwords"));
 
     assertEquals(null, Stage.byName("foobar"));
     assertEquals(null, Stage.byName(null));
   }
 }