Luego recorrió las costas venezolanas desde Curiana (en el sector occidental del actual estado de Falcón) hasta la península de Paraguaná y fundó el 3 de mayo una colonia en la península de la Guajira, en la bahía Honda y la laguna de Cocinetas (cerca del actual Castilletes), a la que llamó "Santa Cruz", que se convirtió en el primer poblado español en territorio continental sudamericano, contando con cabildo y fortaleza.