North Africa and the Saudi peninsula were probably not deserts back then so traveling north from continental Africa was no terrible trek. And the Red Sea was likely shallower and miles narrower, especially at the southern crossing into Yemen at Bab el Mandhib, where the East African Rift Zone, home of most of the earliest humanoid fossils, continues on and becomes the Red Sea. It would have been a natural route for early nomads to follow the Rift Valley north, crossing a narrow gulch into broader flatter lands of the coast of the Arabian peninsula.
Since the original "Out of Africa" hypothesis has been substantially discredited by further research, this appears to be a likely possibility.