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