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.
Just my $.02