How do I perform a reverse history search in ZSH's vi-mode?

You can run bindkey with no arguments to get a list of existing bindings, eg:

# Enter vi mode
chopper:~> bindkey -v

# Search for history key bindings
chopper:~> bindkey | fgrep history
"^[OA" up-line-or-history
"^[OB" down-line-or-history
"^[[A" up-line-or-history
"^[[B" down-line-or-history

In emacs mode, the binding you want is history-incremental-search-backward, but that is not bound by default in vi mode. To bind Ctrl-R yourself, you can run this command, or add it to your ~/.zshrc:

bindkey "^R" history-incremental-search-backward

The zshzle manpage (man zshzle) has more information on zsh's line editor, bindkey, and emacs/vi modes.

This is an ancient question, but the only (and accepted) answer basically tells one how to transplant the “emacs-like” history-incremental-search-backward to vi mode. Whilst this is perfectly doable and may be the right solution for you, it’s a little strange that no one has mentioned the “vi way” of searching history.

vi mode in zsh supports searching history using the standard vi/vim keys: / and ?, both available in command mode. (Hit <Esc> to switch from insert to command mode, just like in vi or vim.)

Their sense is reversed, though: Since you usually want to search your shell’s history in reverse, / does a reverse search whereas ? does a forward search.

Once the first hit is displayed, you can (just like in vi/vim) use n to continue finding more hits in the same direction, or N to reverse the direction of the search.

The relevant default keybindings in the vicmd keymap are:

"/" vi-history-search-backward
"?" vi-history-search-forward
"n" vi-repeat-search
"N" vi-rev-repeat-search