Workflow History is not available as Search Type if you create a New Search when navigating to Lists > Search > Saved Searches > New.
To create a Workflow History Search:
- Create a new search for another type: List > Search > Saved Searches > New > Select any standard record (i.e. Customers, Account, etc)
- Change "searchtype" parameter in the URL to "WorkflowHistory"
Note: You have to spell "WorkflowHistory" as it appears here; otherwise, the url won't work.