Painfully slow, Devel Query logs show culprit
What is the history table?


This is a table for keeping track of what user has read what node. (To show a new/updated message next to it.) 


  Any idea why its taking so long to run the query?


This could be anything, and might be at the server level (not related to Drupal). 

First, check if SQL is slow outside Drupal (eg. PHPmyadmin). Run the same query, see what happens.

If SQL is still slow and you have ssh access to the server, try to run some disk speed checks using sudo hdparm -Tt /dev/sda and dd if=/dev/zero of=/tmp/output bs=8k count=10k; rm -f /tmp/output (assuming Linux). I had a slow site recently that was caused by a malfunctioning hard drive.