It depends on how you define "deleted." If you mean solely on your local device (as in your hard drive) then the answer is no. If you mean in the context of the internet (especially if you have ever signed in with a google account) then the answer is always no, that cannot be erased.
It depends on why you're asking... if you're asking say for example, "can I get my history back?" Then yes, you can if you know what you're doing, then look in your temporary files or use a hard drive recovery program to restore the data. If you're asking, "can the police restore/see my local history" then the answer is most definitely yes. Incognito browsing makes no difference. If you want to truly erase your local hard drive search history, then you need to wipe the entire hard drive over with D-ban (it is free software and will permanently scramble/delete everything, operating system included.)
If you're worried about your search history on Google's servers: too late, it's out there.