It is possible the History folder may be corrupted.
You should be able to delete the folder; it will be re-created.
If you cannot delete it in Regular Mode, try Safe Mode
In IE go to Tools/ Folder Options/ View/ Show Hidden Files and Folders, and you may also want to de-select "hide protected operating system files".
Do a Search for the History folder in this sub-file; \documents and settings\<profile name>\local settings\history