I'm on SP2013 on premise, and this worked for me to show the search box.
First, you have to set the list to be displayable by the browser. I did this through SharePoint Designer, unchecking the 'hide from browser'.
Then, I edited the 'All History' view page, and edited the actual web part for the view. In the miscellaneous section at the bottom, there's an option to 'Display search box'. Check that, save the webpart, save the page. This didn't 'stick' until I did the first step.
The list is shown to be searchable in list settings, but when I tested a search it never brought back any items. But maybe something else is going on timing wise, with it going from a hidden list to a viewable list...