Geological data of the region indicate that the Canary Islands have not been connected to the mainland before. However, fossil evidence suggests some kind of faunal exchange with Africa during the late Neogene. After extensive field work during past years, a re-evaluation of the fossil remains of the first terrestrial vertebrates that settled and thrived on the Canary Islands is presented, with special attention to the long-debated identity of birds that laid large-sized eggs, reported some decades ago on Lanzarote Island. The age of the eggshell-bearing deposits has been recently updated as Early Pliocene (ca. 4 Ma). The dispersal mode of these terrestrial birds to reach the island was an unsolvable challenge in previous studies because the regional geography of the sea bottom was neglected, as well as the chronological succession of events in the formation of the Canary Eastern Ridge, which increased attention to a unique case of arrival of ratites on an island never before united with the mainland. The few animals found in northern Lanzarote (ratites, snakes, turtles, terrestrial snails and bite marks on eggshells pointing to a jagged and unknown large predator) probably made the sea crossing from the mainland in different ways. Two scenarios are contemplated. In both, the circumstances facilitating the faunal transit from Africa to the Canaries ceased after the early Pliocene, around 4 Ma, since these animals have never managed to cross the Canary Channel again.