If you can’t search the history with zsh in GNU screen, check if `Ctrl-R` is issued at all through your terminal, ie. by
$ cat ^R
If this works, append the following keybinding to your `~/.zshrc`:
bindkey '^R' history-incremental-search-backward
(Source)
Thanks man, this was driving me nuts.