[v57+] Places Maintenance is built into Firefox.

Type about:support<enter> in the address bar.

You will find Places Database near the bottom. Press the Verify Integrity button.

When done, copy and post the results here.

Type about:preferences#privacy<enter> in the address bar. The button next to History, select Use Custom Settings.

Turn off Always Use Private Browsing Mode Turn on Remember My Browsing And Download History At the bottom of the page, turn on Clear History When Firefox Closes. At the far right, press the Settings button. Turn on ONLY Cache and Form And Search History leaving the others off.

Are there other devices connected to Sync?

If you use Sync then best is to disconnect Sync temporarily during troubleshooting.

In case you use "Clear history when Firefox closes" or otherwise clear history.

• do not clear the Browsing History

• Options/Preferences -> Privacy & Security
  Firefox will: "Use custom settings for history":
  [X] "Clear history when Firefox closes" -> Settings
• https://support.mozilla.org/en-US/kb/delete-browsing-search-download-history-firefox

• clearing "Site Preferences" clears exceptions for cookies, images, pop-up windows, and software installation and exception for password and other website specific data
• clearing "Cookies" will remove all selected cookies including cookies with an allow exception you may want to keep

FredMcD said

[v57+] Places Maintenance is built into Firefox. Type about:support<enter> in the address bar. You will find Places Database near the bottom. Press the Verify Integrity button. When done, copy and post the results here.

---

Type about:preferences#privacy<enter> in the address bar. The button next to History, select Use Custom Settings.

Turn off Always Use Private Browsing Mode Turn on Remember My Browsing And Download History At the bottom of the page, turn on Clear History When Firefox Closes. At the far right, press the Settings button. Turn on ONLY Cache and Form And Search History leaving the others off.

All my history are gone again... here you go > Task: checkIntegrity + The places.sqlite database is sane + The favicons.sqlite database is sane > Task: invalidateCaches + The caches have been invalidated > Task: checkCoherence + The database is coherent > Task: expire + Database cleaned up > Task: originFrecencyStats + Recalculated origin frecency stats > Task: vacuum + Initial database size is 5120KiB + The database has been vacuumed + Final database size is 5120KiB > Task: stats + Places.sqlite size is 5120KiB + Favicons.sqlite size is 5120KiB + pragma_user_version is 53 + pragma_page_size is 32768 + pragma_cache_size is -2048 + pragma_journal_mode is wal + pragma_synchronous is 1 + History can store a maximum of 112348 unique pages + Table moz_origins has 388 records + Table moz_places has 159 records + Table moz_historyvisits has 13 records + Table moz_inputhistory has 0 records + Table moz_bookmarks has 191 records + Table moz_bookmarks_deleted has 0 records + Table moz_keywords has 0 records + Table sqlite_sequence has 1 records + Table moz_anno_attributes has 0 records + Table moz_annos has 0 records + Table moz_items_annos has 0 records + Table moz_meta has 7 records + Table sqlite_stat1 has 15 records + Index sqlite_autoindex_moz_origins_1 + Index sqlite_autoindex_moz_inputhistory_1 + Index sqlite_autoindex_moz_bookmarks_deleted_1 + Index sqlite_autoindex_moz_keywords_1 + Index sqlite_autoindex_moz_anno_attributes_1 + Index moz_places_url_hashindex + Index moz_places_hostindex + Index moz_places_visitcount + Index moz_places_frecencyindex + Index moz_places_lastvisitdateindex + Index moz_places_guid_uniqueindex + Index moz_places_originidindex + Index moz_historyvisits_placedateindex + Index moz_historyvisits_fromindex + Index moz_historyvisits_dateindex + Index moz_bookmarks_itemindex + Index moz_bookmarks_parentindex + Index moz_bookmarks_itemlastmodifiedindex + Index moz_bookmarks_dateaddedindex + Index moz_bookmarks_guid_uniqueindex + Index moz_keywords_placepostdata_uniqueindex + Index moz_annos_placeattributeindex + Index moz_items_annos_itemattributeindex > Task: _refreshUI

Looks good. Did you do the second part of my post?