I have never used Oh My Zsh, but I use Atuin to do this and it works excellently at that. You can even make it filter by what folder you're in and whether you want to search only this session or host (you can sync shell history across hosts). It never occurred to me that this is something I'd want from a shell prompt, which is what Starship is.