Another way to clear the history (along with other things) IMMEDIATELY is to use the "Reset Safari" option.
I run that almost hourly, not particularly because I don't want anyone to see where I've been, but just to keep Safari running "lean and clean"...