If you're using Opera Sync and syncing history, and you delete certain items in history, see this issue that wipes out all your history.
If not, I'd goto the URL opera://settings/clearBrowserData, clear history for all time, goto the URL opera://about, take note of the "profile" path, close Opera, and delete the "History" file in the profile folder. Then, when you start Opera, it'll create a fresh History file that will hopefully work right.