--- a/mobile/android/base/java/org/mozilla/gecko/db/LocalBrowserDB.java
+++ b/mobile/android/base/java/org/mozilla/gecko/db/LocalBrowserDB.java
@@ -35,32 +35,34 @@ import org.mozilla.gecko.db.BrowserContr
 import org.mozilla.gecko.db.BrowserContract.Thumbnails;
 import org.mozilla.gecko.db.BrowserContract.TopSites;
 import org.mozilla.gecko.distribution.Distribution;
 import org.mozilla.gecko.favicons.decoders.FaviconDecoder;
 import org.mozilla.gecko.favicons.decoders.LoadFaviconResult;
 import org.mozilla.gecko.gfx.BitmapUtils;
 import org.mozilla.gecko.Restrictions;
 import org.mozilla.gecko.sync.Utils;
+import org.mozilla.gecko.sync.repositories.android.BrowserContractHelpers;
 import org.mozilla.gecko.util.GeckoJarReader;
 import org.mozilla.gecko.util.StringUtils;
 
 import android.content.ContentProviderOperation;
 import android.content.ContentResolver;
 import android.content.ContentValues;
 import android.content.Context;
 import android.database.ContentObserver;
 import android.database.Cursor;
 import android.database.MatrixCursor;
 import android.database.MergeCursor;
 import android.graphics.Bitmap;
 import android.graphics.Color;
 import android.graphics.drawable.BitmapDrawable;
 import android.net.Uri;
 import android.support.annotation.CheckResult;
+import android.support.annotation.NonNull;
 import android.text.TextUtils;
 import android.util.Log;
 import org.mozilla.gecko.util.IOUtils;
 
 import static org.mozilla.gecko.util.IOUtils.ConsumedInputStream;
 import static org.mozilla.gecko.favicons.LoadFaviconTask.DEFAULT_FAVICON_BUFFER_SIZE;
 
 public class LocalBrowserDB implements BrowserDB {
@@ -650,27 +652,66 @@ public class LocalBrowserDB implements B
                               limit,
                               null,
                               selection, selectionArgs);
     }
 
     @Override
     public void updateVisitedHistory(ContentResolver cr, String uri) {
         ContentValues values = new ContentValues();
+        long dateVisited = System.currentTimeMillis();
 
         values.put(History.URL, uri);
-        values.put(History.DATE_LAST_VISITED, System.currentTimeMillis());
+        values.put(History.DATE_LAST_VISITED, dateVisited);
         values.put(History.IS_DELETED, 0);
 
         // This will insert a new history entry if one for this URL
         // doesn't already exist
+        String whereClause = History.URL + " = ?";
+        String[] whereArgs = new String[] { uri };
         cr.update(mUpdateHistoryUriWithProfile,
-                  values,
-                  History.URL + " = ?",
-                  new String[] { uri });
+                values,
+                whereClause,
+                new String[]{uri});
+
+        // We need to insert a visit now, but first we need to look up GUID for this history record.
+        String historyGUID = null;
+        Cursor cursor = cr.query(History.CONTENT_URI, new String[]{History.GUID}, whereClause, whereArgs, null);
+        try {
+            if (cursor == null) {
+                Log.e(LOGTAG, "Null cursor while looking up history GUID by url: " + uri);
+                return;
+            }
+
+            if (!cursor.moveToFirst()) {
+                Log.e(LOGTAG, "Empty cursor while looking up history GUID by url: " + uri);
+                return;
+            }
+
+            historyGUID = cursor.getString(
+                    cursor.getColumnIndexOrThrow(History.GUID)
+            );
+        } finally {
+            if (cursor != null) {
+                cursor.close();
+            }
+        }
+
+        if (historyGUID == null) {
+            Log.e(LOGTAG, "Failed to lookup history GUID by url: " + uri);
+            return;
+        }
+
+        // Now that we have a valid history GUID for the given URI, let's insert the visit itself.
+        // Visit type and visit's "is_local" both default to 1 on insertion
+        ContentValues visitValues = new ContentValues();
+        visitValues.put(BrowserContract.Visits.DATE_VISITED, dateVisited);
+        visitValues.put(BrowserContract.Visits.HISTORY_GUID, historyGUID);
+
+        cr.insert(BrowserContract.Visits.CONTENT_URI, visitValues);
     }
 
     @Override
     public void updateHistoryTitle(ContentResolver cr, String uri, String title) {
         ContentValues values = new ContentValues();
         values.put(History.TITLE, title);
 
         cr.update(mHistoryUriWithProfile,
@@ -747,27 +788,63 @@ public class LocalBrowserDB implements B
         Uri url = mHistoryExpireUriWithProfile;
         url = url.buildUpon().appendQueryParameter(BrowserContract.PARAM_EXPIRE_PRIORITY, priority.toString()).build();
         cr.delete(url, null, null);
     }
 
     @Override
     @RobocopTarget
     public void removeHistoryEntry(ContentResolver cr, String url) {
+        // We need to handle the visits before delete call for the history record, since that wipes
+        // away all of the data from that record except for the GUID - so we won't be able to figure out
+        // which visits to remove.
+        int visitsDeleted = deleteVisitsForURL(cr, url);
+        Log.d(LOGTAG, "Deleted " + visitsDeleted + " for url: " + url);
+
         cr.delete(mHistoryUriWithProfile,
                   History.URL + " = ?",
                   new String[] { url });
     }
 
+    /**
+     * Utility function to look up history GUID for given url, and delete associated visits.
+     * Assuming 1-1 mapping of URLs to GUIDs in the history table.
+     *
+     * @param cr <code>ContentResolver</code> used for history GUID lookup and deletion
+     * @param url URL used to look up history GUID
+     * @return Number of visits deleted
+     */
+    private int deleteVisitsForURL(@NonNull ContentResolver cr, @NonNull String url) {
+        Cursor cursor = cr.query(
+                BrowserContractHelpers.HISTORY_CONTENT_URI,
+                new String[] {History.GUID}, History.URL + " = ?", new String[] {url}, null);
+        if (cursor == null) {
+            return 0;
+        }
+        try {
+            if (!cursor.moveToFirst()) {
+                return 0;
+            }
+            String guid = cursor.getString(cursor.getColumnIndex(History.GUID));
+            return cr.delete(
+                    BrowserContractHelpers.VISITS_CONTENT_URI,
+                    BrowserContract.Visits.HISTORY_GUID + " = ?", new String[]{guid}
+            );
+        } finally {
+            cursor.close();
+        }
+    }
+
     @Override
     public void clearHistory(ContentResolver cr, boolean clearSearchHistory) {
         if (clearSearchHistory) {
             cr.delete(mSearchHistoryUri, null, null);
         } else {
             cr.delete(mHistoryUriWithProfile, null, null);
+            cr.delete(BrowserContractHelpers.VISITS_CONTENT_URI, 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