There are plenty of whale skeletons sticking up out of the Sahara Desert today.
They have legs. Not even that old. Whales without legs are a pretty recent phenomenon. They only recently lost their legs. And the Sahara was green just 6000 years ago. Probably where they got the garden of Eden story from.