--- a/mobile/android/base/java/org/mozilla/gecko/BrowserApp.java
+++ b/mobile/android/base/java/org/mozilla/gecko/BrowserApp.java
@@ -2004,17 +2004,20 @@ public class BrowserApp extends GeckoApp
 
             case "Sanitize:OpenTabs":
                 Tabs.getInstance().closeAll();
                 callback.sendSuccess(null);
                 break;
 
             case "Sanitize:ClearHistory":
                 BrowserDB.from(getProfile()).clearHistory(
-                        getContentResolver(), message.getBoolean("clearSearchHistory", false));
+                        getContentResolver(),
+                        message.getBoolean("clearSearchHistory", false),
+                        message.getLong("startTime", 0)
+                    );
                 callback.sendSuccess(null);
                 break;
 
             case "Sanitize:ClearSyncedTabs":
                 FennecTabsRepository.deleteNonLocalClientsAndTabs(this);
                 callback.sendSuccess(null);
                 break;
 

--- a/mobile/android/base/java/org/mozilla/gecko/db/BrowserDB.java
+++ b/mobile/android/base/java/org/mozilla/gecko/db/BrowserDB.java
@@ -93,17 +93,17 @@ public abstract class BrowserDB {
     @Nullable public abstract Cursor getHistoryForURL(ContentResolver cr, String uri);
 
     public abstract long getPrePathLastVisitedTimeMilliseconds(ContentResolver cr, String prePath);
 
     public abstract void expireHistory(ContentResolver cr, ExpirePriority priority);
 
     public abstract void removeHistoryEntry(ContentResolver cr, String url);
 
-    public abstract void clearHistory(ContentResolver cr, boolean clearSearchHistory);
+    public abstract void clearHistory(ContentResolver cr, boolean clearSearchHistory, long since);
 
 
     public abstract String getUrlForKeyword(ContentResolver cr, String keyword);
 
     public abstract boolean isBookmark(ContentResolver cr, String uri);
     public abstract boolean addBookmark(ContentResolver cr, String title, String uri);
     public abstract Uri addBookmarkFolder(ContentResolver cr, String title, long parentId);
     @Nullable public abstract Cursor getBookmarkForUrl(ContentResolver cr, String url);

--- a/mobile/android/base/java/org/mozilla/gecko/db/BrowserProvider.java
+++ b/mobile/android/base/java/org/mozilla/gecko/db/BrowserProvider.java
@@ -558,16 +558,21 @@ public class BrowserProvider extends Sha
                     return type;
                 }
 
                 debug("URI has unrecognized type: " + uri);
                 return null;
         }
     }
 
+    public Long isCallerHaveSince(Uri uri) {
+        String since = uri.getQueryParameter("since");
+        return Long.parseLong(since);
+    }
+
     @SuppressWarnings("fallthrough")
     @Override
     public int deleteInTransaction(Uri uri, String selection, String[] selectionArgs) {
         trace("Calling delete in transaction on URI: " + uri);
         final SQLiteDatabase db = getWritableDatabase(uri);
 
         final int match = URI_MATCHER.match(uri);
         int deleted = 0;
@@ -593,30 +598,47 @@ public class BrowserProvider extends Sha
 
                 selection = DBUtils.concatenateWhere(selection, TABLE_HISTORY + "._id = ?");
                 selectionArgs = DBUtils.appendSelectionArgs(selectionArgs,
                         new String[] { Long.toString(ContentUris.parseId(uri)) });
                 // fall through
             case HISTORY: {
                 trace("Deleting history: " + uri);
                 beginWrite(db);
+
                 /**
-                 * Deletes from Sync are actual DELETE statements, which will cascade delete relevant visits.
-                 * Fennec's deletes mark records as deleted and wipe out all information (except for GUID).
-                 * Eventually, Fennec will purge history records that were marked as deleted for longer than some
-                 * period of time (e.g. 20 days).
-                 * See {@link SharedBrowserDatabaseProvider#cleanUpSomeDeletedRecords(Uri, String)}.
+                 * Deletes from history table, when since is available. Its special case, which is
+                 * being used by our removeHistory method of browsingData API of Web-Extension. Due to its
+                 * only consumer, we are not updating any previous workflow.
                  */
-                final ArrayList<String> historyGUIDs = getHistoryGUIDsFromSelection(db, uri, selection, selectionArgs);
-
-                if (!isCallerSync(uri)) {
-                    deleteVisitsForHistory(db, historyGUIDs);
-                }
-                deletePageMetadataForHistory(db, historyGUIDs);
-                deleted = deleteHistory(db, uri, selection, selectionArgs);
+
+                Long since = isCallerHaveSince(uri);
+                if (since > 0) {
+                    // Get all history_guids which are needed to be removed
+                    ArrayList<String> historyGUIDs = getHistoryGUIDsFromSelection(db, uri, History.DATE_LAST_VISITED + ">=" + since, null);
+
+                    // Delete visits from visit table.
+                    deleteVisitsWithSince(db, historyGUIDs, since);
+                    // Update and mark orphaned items records as deleted from history table
+                    deleted = bulkUpdateDeleteHistoryTable(db, uri, historyGUIDs);
+                } else {
+                    /**
+                     * Deletes from Sync are actual DELETE statements, which will cascade delete relevant visits.
+                     * Fennec's deletes mark records as deleted and wipe out all information (except for GUID).
+                     * Eventually, Fennec will purge history records that were marked as deleted for longer than some
+                     * period of time (e.g. 20 days).
+                     * See {@link SharedBrowserDatabaseProvider#cleanUpSomeDeletedRecords(Uri, String)}.
+                     */
+                    final ArrayList<String> historyGUIDs = getHistoryGUIDsFromSelection(db, uri, selection, selectionArgs);
+                    if (!isCallerSync(uri)) {
+                        deleteVisitsForHistory(db, historyGUIDs);
+                    }
+                    deletePageMetadataForHistory(db, historyGUIDs);
+                    deleted = deleteHistory(db, uri, selection, selectionArgs);
+                 }
                 deleteUnusedImages(uri);
                 break;
             }
 
             case VISITS:
                 trace("Deleting visits: " + uri);
                 beginWrite(db);
                 deleted = deleteVisits(uri, selection, selectionArgs);
@@ -2298,16 +2320,148 @@ public class BrowserProvider extends Sha
                     DBUtils.computeSQLInClause(chunkGUIDs.size(), historyGUIDColumn),
                     chunkGUIDs.toArray(new String[chunkGUIDs.size()])
             );
         }
 
         return deleted;
     }
 
+    private int deleteVisitsWithSince(SQLiteDatabase db, ArrayList<String> historyGUIDs, Long since) {
+        // Due to SQLite's maximum variable limitation, we need to chunk our delete statements.
+        // For example, if there were 1200 GUIDs, this will perform 2 delete statements if SQLITE_MAX_VARIABLE_NUMBER is 999.
+        int deleted = 0;
+        for (int chunk = 0; chunk <= historyGUIDs.size() / DBUtils.SQLITE_MAX_VARIABLE_NUMBER; chunk++) {
+            final int chunkStart = chunk * DBUtils.SQLITE_MAX_VARIABLE_NUMBER;
+            int chunkEnd = (chunk + 1) * DBUtils.SQLITE_MAX_VARIABLE_NUMBER;
+            if (chunkEnd > historyGUIDs.size()) {
+                chunkEnd = historyGUIDs.size();
+            }
+            final List<String> chunkGUIDs = historyGUIDs.subList(chunkStart, chunkEnd);
+            deleted += db.delete(
+                    Visits.TABLE_NAME,
+                    DBUtils.computeSQLInClause(chunkGUIDs.size(), Visits.HISTORY_GUID) + " AND " + Visits.DATE_VISITED + " >= " + since,
+                    chunkGUIDs.toArray(new String[chunkGUIDs.size()])
+            );
+        }
+
+        return deleted;
+    }
+
+    private int deleteHistoryByHistoryGuids(SQLiteDatabase db, Uri uri, ArrayList<String> historyGUIDs) {
+        // Due to SQLite's maximum variable limitation, we need to chunk our delete statements.
+        // For example, if there were 1200 GUIDs, this will perform 2 delete statements if SQLITE_MAX_VARIABLE_NUMBER is 999.
+        int deleted = 0;
+        for (int chunk = 0; chunk <= historyGUIDs.size() / DBUtils.SQLITE_MAX_VARIABLE_NUMBER; chunk++) {
+            final int chunkStart = chunk * DBUtils.SQLITE_MAX_VARIABLE_NUMBER;
+            int chunkEnd = (chunk + 1) * DBUtils.SQLITE_MAX_VARIABLE_NUMBER;
+            if (chunkEnd > historyGUIDs.size()) {
+                chunkEnd = historyGUIDs.size();
+            }
+            final List<String> chunkGUIDs = historyGUIDs.subList(chunkStart, chunkEnd);
+            deleted += deleteHistory(db,
+                uri,
+                DBUtils.computeSQLInClause(chunkGUIDs.size(), History.GUID),
+                chunkGUIDs.toArray(new String[chunkGUIDs.size()])
+            );
+        }
+        return deleted;
+    }
+
+    private int bulkUpdateDeleteHistoryTable(SQLiteDatabase db, Uri uri, ArrayList<String> historyGUIDs) {
+
+        String coloumns[] = { Visits.HISTORY_GUID, "count(" + Visits.HISTORY_GUID + ") as count",
+                              "max(" + Visits.DATE_VISITED + ") as date", Visits.IS_LOCAL };
+        String groupBy = Visits.HISTORY_GUID + "," + Visits.IS_LOCAL;
+
+        // To strore data.
+        String historyGuid;
+        long localDate, remoteDate;
+        int localCount, remoteCount, isLocal;
+        ContentValues values = new ContentValues();
+
+        Cursor cursor;
+        for (int chunk = 0; chunk <= historyGUIDs.size() / DBUtils.SQLITE_MAX_VARIABLE_NUMBER; chunk++) {
+            final int chunkStart = chunk * DBUtils.SQLITE_MAX_VARIABLE_NUMBER;
+            int chunkEnd = (chunk + 1) * DBUtils.SQLITE_MAX_VARIABLE_NUMBER;
+            if (chunkEnd > historyGUIDs.size()) {
+                chunkEnd = historyGUIDs.size();
+            }
+            final List<String> chunkGUIDs = historyGUIDs.subList(chunkStart, chunkEnd);
+
+            // Retrieve Data to update History Table
+            cursor = db.query(
+                    Visits.TABLE_NAME,
+                    coloumns,
+                    DBUtils.computeSQLInClause(chunkGUIDs.size(), Visits.HISTORY_GUID),
+                    chunkGUIDs.toArray(new String[chunkGUIDs.size()]),
+                    groupBy,
+                    null,
+                    Visits.HISTORY_GUID,
+                    null
+            );
+
+            // Update History Table
+            while (cursor.moveToNext()) {
+                localDate = remoteDate = 0L;
+                localCount = remoteCount = 0;
+
+                historyGuid = cursor.getString(cursor.getColumnIndexOrThrow(Visits.HISTORY_GUID));
+                isLocal = cursor.getInt(cursor.getColumnIndexOrThrow(Visits.IS_LOCAL));
+
+                // Due to fact that remote will always come first and then remote.
+                if (isLocal == 0) {
+                    remoteCount = cursor.getInt(cursor.getColumnIndexOrThrow("count"));
+                    remoteDate = cursor.getLong(cursor.getColumnIndexOrThrow("date"));
+
+                    // Check if same historyGuid has local visit
+                    if (cursor.moveToNext()) {
+                        if (cursor.getString(cursor.getColumnIndexOrThrow(Visits.HISTORY_GUID)).equals(historyGuid) &&
+                            cursor.getInt(cursor.getColumnIndexOrThrow(Visits.IS_LOCAL)) == 1) {
+                            localCount = cursor.getInt(cursor.getColumnIndexOrThrow("count"));
+                            localDate = cursor.getLong(cursor.getColumnIndexOrThrow("date"));
+                        } else {
+                            localCount = 0;
+                            localDate = 0L;
+                            // Move back if different history_guid
+                            cursor.moveToPrevious();
+                        }
+                    }
+                } else {
+                    localCount = cursor.getInt(cursor.getColumnIndexOrThrow("count"));
+                    localDate = cursor.getLong(cursor.getColumnIndexOrThrow("date"));
+
+                    remoteCount = 0;
+                    remoteDate = 0L;
+                }
+
+                // Clear content values
+                values.clear();
+                // Put values to content values
+                values.put(History.VISITS, localCount + remoteCount);
+                values.put(History.LOCAL_VISITS, localCount);
+                values.put(History.REMOTE_VISITS, remoteCount);
+                values.put(History.LOCAL_DATE_LAST_VISITED, localDate);
+                values.put(History.REMOTE_DATE_LAST_VISITED, remoteDate);
+                values.put(History.DATE_LAST_VISITED, localDate > remoteDate ? localDate : remoteDate);
+
+                db.update(History.TABLE_NAME, values, History.GUID + "='" + historyGuid + "'", null);
+
+                // If present in table, not an orphaned items, so remove from historyGuids list
+                historyGUIDs.remove(historyGuid);
+            }
+        }
+        // Delete Orphaned history Items
+        int deleted = deleteHistoryByHistoryGuids(db, uri, historyGUIDs);
+        // Delete Metadata
+        deletePageMetadataForHistory(db, historyGUIDs);
+
+        return deleted;
+    }
+
     /**
      * Chunk our deletes around {@link DBUtils#SQLITE_MAX_VARIABLE_NUMBER} so that we don't stumble
      * into 'too many SQL variables' error.
      */
     private int bulkDeleteByBookmarkGUIDs(SQLiteDatabase db, Uri uri, List<String> bookmarkGUIDs) {
         // Due to SQLite's maximum variable limitation, we need to chunk our update statements.
         // For example, if there were 1200 GUIDs, this will perform 2 update statements.
         int updated = 0;

--- a/mobile/android/base/java/org/mozilla/gecko/db/LocalBrowserDB.java
+++ b/mobile/android/base/java/org/mozilla/gecko/db/LocalBrowserDB.java
@@ -841,21 +841,26 @@ public class LocalBrowserDB extends Brow
     @RobocopTarget
     public void removeHistoryEntry(ContentResolver cr, String url) {
         cr.delete(mHistoryUriWithProfile,
                   History.URL + " = ?",
                   new String[] { url });
     }
 
     @Override
-    public void clearHistory(ContentResolver cr, boolean clearSearchHistory) {
+    public void clearHistory(ContentResolver cr, boolean clearSearchHistory, long since) {
         if (clearSearchHistory) {
             cr.delete(mSearchHistoryUri, null, null);
         } else {
-            cr.delete(mHistoryUriWithProfile, null, null);
+            // Pass since as URI param
+            final Uri newHistoryUriWithProfile = mHistoryUriWithProfile.buildUpon()
+                                                        .appendQueryParameter("since", Long.toString(since))
+                                                        .build();
+
+            cr.delete(newHistoryUriWithProfile, null, null);
         }
     }
 
     private void assertDefaultBookmarkColumnOrdering() {
         // We need to insert MatrixCursor values in a specific order - in order to protect against changes
         // in DEFAULT_BOOKMARK_COLUMNS we can just assert that we're using the correct ordering.
         // Alternatively we could use RowBuilder.add(columnName, value) but that needs api >= 19,
         // or we could iterate over DEFAULT_BOOKMARK_COLUMNS, but that gets messy once we need

--- a/mobile/android/geckoview/src/main/java/org/mozilla/gecko/util/GeckoBundle.java
+++ b/mobile/android/geckoview/src/main/java/org/mozilla/gecko/util/GeckoBundle.java
@@ -240,16 +240,39 @@ public final class GeckoBundle {
      * @return Int array value
      */
     public int[] getIntArray(final String key) {
         final Object value = mMap.get(key);
         return value == null ? null : Array.getLength(value) == 0 ? EMPTY_INT_ARRAY :
                value instanceof double[] ? getIntArray((double[]) value) : (int[]) value;
     }
 
+    /** Returns the value associated with an long mapping, or defaultValue if the mapping
+     * does not exist.
+     *
+     * @param key Key to look for.
+     * @param defaultValue Value to return if mapping does not exist.
+     * @return Long value
+     */
+    public long getLong(final String key, final long defaultValue) {
+        final Object value = mMap.get(key);
+        return value == null ? defaultValue : ((Number) value).longValue();
+    }
+
+    /**
+     * Returns the value associated with an long mapping, or 0 if the mapping does not
+     * exist.
+     *
+     * @param key Key to look for.
+     * @return Long value
+     */
+    public long getLong(final String key) {
+        return getLong(key, 0L);
+    }
+
     /**
      * Returns the value associated with a String mapping, or defaultValue if the mapping
      * does not exist.
      *
      * @param key Key to look for.
      * @param defaultValue Value to return if mapping does not exist.
      * @return String value
      */