Google app clinging to my history no matter what

I have young kids, so I don't want them to see every place I go. Yet when I open the Google app on my Samsung S4 and start to type something, anything, a dropdown appeared showing a history of several sites. Even when I held down on each one and selected "Delete" (it was in red for some reason), it wouldn't delete it. Even deleting the cache in Applications made no change. I had to uninstall updates before it finally reverted to a former version before this history was removed. Am I missing something simple? If Google is going to track me this closely and give me this much trouble to remove history, I'll go to another search engine in a heartbeat.