Knowing something of Espanola, and of the Admiral also, and reading in the despatches of the turbulent condition of the colony, he had a shrewd idea that Columbus's hands would be kept pretty full in Espanola itself, and that he would have no opportunity for some time to make any more voyages of discovery.

He therefore represented to Fonseca what a pity it would be if all this revenue should remain untapped just because one man had not time to attend to it, and he proposed that he should take out an expedition at his own cost and share the profits with the Crown.
This proposal was too tempting to be refused; unlike the expeditions of Columbus, which were all expenditure and no revenue, it promised a chance of revenue without any expenditure at all.

The Paria coast, having been discovered subsequent to the agreement made with Columbus, was considered by Fonseca to be open to private enterprise; and he therefore granted Ojeda a licence to go and explore it.

Among those who went with him were Amerigo Vespucci and Columbus's old pilot, Juan de la Cosa, as well as some of the sailors who had been with the Admiral on the coast of Paria and had returned in the caravels which had brought his account of it back to Spain.

Ojeda sailed on May 20, 1499; made a landfall some hundreds of miles to the eastward of the Orinoco, coasted thence as far as the island of Trinidad, and sailed along the northern coast of the peninsula of Paria until he came to a country where the natives built their hots on piles in the water, and to which he gave the name of Venezuela.