This question comes up pretty often (which doesn't really say anything bad about you, just that this rule is very well hidden.)
The answer is that they would need 5 levels of Fighter to take the class, but between you and me, I would let a character take it at 4th, assuming 1st level in the PrC gave +1 BAB.
Designers have generally pointed to "Level Advancement" on PH p. 145 as a series of mandatory ordered steps. Hence "1. Choose class" comes before the "2. Base Attack Bonus" increase which would satisfy the particular prerequisite.