How do I delete my search history on Firefox?

[NickelsnDimes]

When I start typing something into a search engine it shows everything I have searched for in the past.
This happens even after I go to History>Show All History> then delete everything.

Thanks for the help.