In 1434 (or 1433) one of Prince Henry's household squires, Gil Eanes, sailed past Cape Bojador, in present day Western Sahara, the physical and psychological barrier which European sailors had long considered the non plus ultra of navigation.

In the follow-up trip of 1435, Henry sent Eanes out again, this time accompanied by a second ship, a barinel under the command of Afonso Gonçalves Baldaia, with instructions to explore the coast beyond Bojador.

[2] There is scant information on the barinel, other than that it was a new deep-hulled, two-masted sail-and-oar-powered ship, larger than Eanes's single-mast barca and said to be especially designed for coastal exploring (and thus might have already had a lateen sail in the mizzen mast).

Sailing primarily along the largely deserted coast of the Western Sahara, Eanes and Baldaia saw some traces of human presence - footprints of men and camels - but encountered no one on this expedition.

Proceeding south, Baldaia discovered a coastal inlet which he named Rio do Ouro (around modern Dakhla, Western Sahara), imagining it was the mouth of the legendary 'River of Gold' spoken of by Trans-Saharan traders (probably a reference to the Senegal River, which reached deep into the Mali Empire).

It was only in 1441 that Henry finally followed up on it and sent out two ships, prototypes of the new lateen-rigged caravel - one under Antão Gonçalves to return to Rio do Ouro to undertake another seal hunt, and another under Nuno Tristão, to explore beyond Baldaia's furthest point, Pedra da Galé.