From 6.5 to 5.5 million years ago, the Mediterranean Sea underwent what scientists called "The Messinian Salinity Crisis". In basic description, some geological force (I'm not sure what) simply...
...dried it up.
The key to this question is that with a major body of land reduced to land, passage is open for animals to colonize new lands. Turning lots of water into land is, at first, the most convenient.
The thing is, the Crisis happened only once. Once the waters from the Atlantic broke through Gibraltar, the Mediterranean stayed a sea for the last five million years. For the sake of animal migration, in an alternate universe, should it make sense for the Mediterranean drying up only to refill with water to be a cyclical event, preferably earlier than seven million years? Or should I stick to travel via wind and rafts, as had often happened more than once?