I think the Pentium is more or less the first microprocessor with branch prediction. Certainly the most mainstream.

PowerPC 601 arrived at more or less the same time, and the Alpha 21064 was a year earlier. There were a few minicomputers and mainframes before that with branch predictors.

Arguably the 486 could have done with a branch predictor (even a single entry loop predictor would have helped), and maybe the 386 too. But microcoded CISC designs didn't benefit much from predictors because they have multiple cycles to work it out.

And RISC cpus were in their "branch delay slots are awesome" phase throughout most of the 80s. With a bit of trickery (very simple branch conditions and a 2 phase clock), your classic 5-stage MIPS design can fully hide all branches with just a single branch delay slot, so they were a little slow to adopt predictors.

I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be.