Click the Firefox button, go to Add-ons, then Extensions and uninstall the Ask Toolbar.

You are using Delete browsing, search and download history on Firefox to clear your private data on exit.
The default settings include clearing the Browsing History, so if you want to keep history then you need to exclude that.

• Tools > Options > Privacy > History: Firefox will: "Use custom settings for history" : [X] Clear history when Firefox closes > Settings

Also make sure that you not run Firefox in permanent Private Browsing - Use Firefox without saving history mode.

• You enter Private Browsing mode if you select: Tools > Options > Privacy > History: Firefox will: "Never Remember History"
• To see all History and Cookie settings, choose: Tools > Options > Privacy, choose the setting Firefox will: Use custom settings for history
• Uncheck: [ ] "Permanent Private Browsing mode"

Another possible cause is a problem with the file places.sqlite that stores the bookmarks and the history.

• http://kb.mozillazine.org/Bookmarks_history_and_toolbar_buttons_not_working_-_Firefox

Nup, removing the tool bar and tweaking history settings in all combinations didn't help. Firefox still deletes my history randomly. Will try deleting places.sqlite file.

Are you using cleanup software like CCleaner?

Looks like the new update of CCleaner was the culprit. It would clean files in the background without me noticing, I tweaked the settings a bit and my life's back to normal again :D Quite a shifty update though, never had this problem before.