Lacosa dibujó el perfil del nuevo país y le dio nombre. Con este hecho se convirtió en el padrino de Venezuela, proclamado ya por este país. En este viaje de Lacosa, 1499, se fundó en la Goajira la primera ciudad, en tierra hoy colombiana. La exploración y conquista de Nueva Granada (hoy Colombia), Venezuela, llamada gran parte de ella Nueva Andalucía y Ecuador, deben tratarse conjuntamente, exceptuando las primeras acciones. En 1516 el franciscano P. Juan Garcés estableció una misión en Cumaná. Los dominicos hicieron lo mismo en Píritu y Chiribichi. Pero en 1519 ya habían sido arrasadas por los indios. En 1521 el colono de Santo Domingo, Rodrigo de Bastida obtine permiso para explorar Tierra Firme. En 1522 Pascual de Andagoya, visitador de Indios, desde Panamá, descubre la costa colombiana del río San Juan y recibe información sobre el imperio incaico. Náufrago y enfermo, pero con un cacique a bordo, vuelve a Panamá. En 1525, Rodrigo de Bastida funda Santa Marta, pero cesa en sus exploraciones y abandona la empresa. De 1527 en adelante, Juan de Ampiés reanuda las exploraciones y funda Coro y Tocuyo.
En 1528, el emperador, agobiado por las deudas, cede los derechos de explorar y explorar el nuevo país a los banqueros alemanes Welser, que iniciron sus exploraciones en 1519 con la fundación de Maracaibo. Las expediciones de Alfinger, Federmann, Hobermunt y Hutten son famosas. Pero el gobernador Juan de Carvajal acabó con estas actividades ejecutando injustamente al joven Felipe de Hutten. El licendiado Pérez de Tolosa, enviado por Carlos I, tomó jicio de residencia a Carvajal y lo condenó a muerte. En 1529, Diego de Orgaz, castellano originario de las Encartaciones, explora las bocas del Orinoco. En 1532 Pedro de Heredia explora el río Magdalena y al año siguiente funda Cartagena de Indias. En abril de 1536, Gonzalo Jiménez de Quedad comienza la exploración del Magdalena y el Opón. El 6 de agosto de 1538 funda Santa Fe de Bogotá y da al país conquistado el nombre de Nueva Granada. Sebastián de Benalcázar había fundado San Francisco de Quito en 1534. Con autorización de Francisco Pizarro, se encaminaba también a Colombia y fundaba en 1536 y 1537 las ciudades de Cali y Popayan. En las llanuras de Bogotá se encontraron Quesada, Benalcázar y Federman, procedentes estos dos últimos de Ecuador y Venezuela. Quesada supo ganarse a los hambrientos soldados de Federmann y celebró un pacto con Benalcázar. En febrero de 1539 entraron juntos en la actual Bogotá y en abril nombraron alcaldes y regidores. Para los detalles del segundo vije de Andagoya a su gobernación de San Juan, en Colombia.
En 1539, desde Calí, Lorenzo de Aldana ordena a Jorge Robledo la fundación de Ancerma y nombra como uno de los primeros alcaldes a Martín de Amaroto. El mismo año, Lorenzo de Aldana funda Pasto. Aldana y Benalcázar obraban amparados en Pizarro, cuya jurisdicción alcanzaba hasta esas tierras. Benalcázar habría de expulsar de su gobernación a Pascual de Andagoya que dejó a su hijo en Buenaventura. En 1544 llega a Nueva Granada, como visitador imperial, Miguel Díez de Armendáriz con facultades para inspeccionar las cuatro gobernaciones del territorio: Cartagena de Indias, Santa Marta, San Juan y Popayán. En 1545 llegó su sobrino Pedro de Ursúa a quien nombró comisionado suyo en Santa Fe. Armendáriz tomó juicio de residencia a los hermanos Heredia. Pedro de Ursúa fundó Pamplona en 1547 y también Tudela. Luego fue justicia Mayor de Santa Marta, cayó en desgracia y pasó a Panamá. Intervino en varias guerras y finalmente en la expedición de Lope de Aguirre al Dorado. La creación de las Audiencias, entre ellas la de Bogotá en 1550, inicia la época colonial aunque siguen aún las conquistas tardías. Ya se enumeraron las que partieron de Méjico a las que podríamos agregar las de Trinidad y Guayana por Berrio. La llegada de Lope de Aguirre a la isla Margarita y su aventura venezolana es el episodio más dramático del siglo XVI.