The only solution I've found was to 1) exit Opera 2) delete the History file in the profile folder 3) restart Opera
Since then History works again.
I can only assume that somehow the history file became corrupted, it didn't have actual entries inside before deleting (checked with a hex viewer).