2 suggestions, but not sure either will work.
One possibility is that it may be down to a corrupt index.dat file in the History folder. Try deleting the file (more below). Windows will re-create the file when it reloads, hopefully a clean one, and see if that works.
Before you do that, try the obvious first. Close IE. Go to Control Panel, Internet Options, General tab to Clear History. Restart IE, visit a couple of sites, and try History.
If there is still no history, try deleting the index.dat file.
The file is at C:\Documents and Settings\[Username]\Local Settings\History\History.IE5\index.dat
However, when you are logged on to the particular [Username], you cannot see this file (or in fact the History.IE5 folder), even if you enable Show all Hidden Files and turn off Hide protected operating system files. And you can't delete it when you are logged on.
If you have another user account with Administrator privileges, log off the problematic User, and log on to the other user. Navigate to the History.IE5 folder.
I suggest you delete all the contents within the History.IE5 folder (including subfolders). The files and folders will be re-created by Windows when you log back on to that user.
Log back on to the problematic User, open IE and test History again.
If you don't have another user account with Administrator privileges, you can create one. Alternatively, download a program which can delete index.dat files for you.
click here and select one of the free programs which can delete index.dat files for you (such as System Security Suite).
Alternatively you can try repairing IE. click here for instructions. You will have to reinstall IE updates afterwards.