The history-beginning-search-backward widget, which is standard to the zsh line editor, does it. You don't need to pull in all of oh-my-zsh.

To use it, I use:

  bindkey "^[[A" history-beginning-search-backward

This seems to have been broken for me unless I add DEBIAN_PREVENT_KEYBOARD_CHANGES=yes to my .zshenv. I'm not sure if it was an update to ZSH, oh-my-zsh, or Ubuntu that causes the issue.

Im using oh-my-zsh, but I cant find this one. Care to enlighten me which option or plugin I should enable? :)

Edit: Seems ctrl-up and ctrl-down does the trick.

I'm using https://github.com/zsh-users/zsh-history-substring-search

It emulates the Fish behavior (which is just awesome). I'm not sure if it requires oh-my-zsh, but I think it doesn't.

It's actually a plugin bundled with oh-my-zsh, but I copy-pasted the default keybindings from the github page you linked, and it's indeed pretty awesome.