fzf [0] has a history mode included and integrates nicely with fish. You just need to enable the fzf bindings [1], then CTRL-r will give you a (fzf) history searcher.

[0] https://wiki.archlinux.org/index.php/Fzf#fish

[1] https://github.com/junegunn/fzf