There are two ways Out of Africa if you have only the ability to walk and use primitive boats. One is to cross the Sinai Peninsula to the Levant. The other is the cross the short and shallow bodies of water in the Gate of Tears at the other end of the Red Sea into Southern Arabia. (Arguably, you could also cross the Strait of Gibraltar, but this is a more difficult waterway to cross with a very primitive boat and there is really no evidence of this route being used by modern humans until ca. 40 kya.)
A number of recent archaeological finds have identified stone tools and structures in the interior of Arabia (which is basically enclosed and separated from the coast by a ring of low, old mountains) in the 120 kya to 100 kya range that are strikingly similar to contemporaneous Nubian stone tools and structures found in association with modern human remains in Africa in what is today called Sudan.
Now, these tools have also been found in what is now Israel. This supports a possible Levatine route out of Africa for first wave modern humans (alternately, a Gate of Tears population could have migrated from interior Arabia to the Levant, or both), something that 100 kya anatomically modern human remains in the Levant had already established, and it connects those Levantine remains to the Nubian material culture. At a minimum, this adds to the body of evidence that the earliest Out of Africa migration by modern humans is much older than what contemporary and ancient DNA genetics based estimates suggest.
It also helps to establish at least one particular African archaeological culture of the Middle Paleolithic as the source, or at least one of the sources, for the Out of Africa population, as opposed to what has until recent years been a purely hypothetical pre-Out of Africa Northeast African population.
It isn't entirely clear if these early Arabian and Levantine modern humans are ancestral to modern humans found later in the same region (and possibly also in South Asia were there are modern human tools pre-75 kya, and East Asia where there is increasingly strong evidence of modern humans pre-100 kya possibly arriving via a northern route*).
TMCRA of non-Africans by genetic means is on the order of 60 kya +/- 10 kya or so, by multiple independent genetic methods. This could imply (A) a sustained period with a small first wave Out of Africa population that experienced a bottleneck slightly before then that purged other lineages, or (B) it could imply replacement by another wave of Out of Africa modern humans (with the earlier data points being the "Out of Africa that failed" leaving only slight archaeological traces and some admixture with Neanderthals ancestral to the Altai Neanderthals - not necessarily anywhere near the Altai mountain region), or (C) it could imply that there is a methodological flaw, probably in the genetics based dating, that is distorting the estimates.
It isn't clear what archaeological cultures in Northeast Africa and Southwest Asia exist in the early Upper Paleolithic that could be identified with a migration that is a better fit to the genetics based dates. We also don't have any ancient DNA from Africa, Southwest Asia or East Asia for "first wave Out of Africa" populations.
* I am close to the tipping point where I feel that I can take this evidence seriously, despite its deviation from well established paradigms, based upon scholarly articles and pre-prints that I've read in the last couple of weeks.