En 1498, en el marco de su Tercer Viaje, el almirante Cristóbal Colón navegó cerca del Delta del Orinoco, para luego internarse en el golfo de Paria. Maravillado, Colón expresa en su emotiva carta a los Reyes Católicos su seguridad de haber llegado al paraíso terrenal, y confundido por la inusual salobridad de las aguas, escribe:
"...Torno a mi propósito referente a la Tierra de Gracia, al río y lago que allí hallé, tan grande que más se le puede llamar mar que lago, porque lago es lugar de agua, y en siendo grande se le llama mar, por lo que se les llama de esta manera al de Galilea y al Muerto. Y digo que si este río no procede del Paraíso Terrenal, viene y procede de tierra infinita, del Continente Austral, del cual hasta ahora no se ha tenido noticia; mas yo muy asentado tengo en mi ánima que allí donde dije, en Tierra de Gracia, se halla el Paraíso Terrenal."
Colón denominó a estos parajes paradisíacos como «Tierra de Gracia», expresión que ha prevalecido hasta el día de hoy como seudónimo del país. Pero al año siguiente, una expedición comandada por Alonso de Ojeda recorrió la costa del territorio hasta llegar a la entrada del actual lago de Maracaibo, en un golfo localizado entre las penínsulas de Paraguaná y de la Guajira. En aquella travesía, la tripulación observó las viviendas construidas por los indígenas añú, erigidas sobre pilotes de madera que sobresalían del agua. Dichos palafitos le recordaron a Américo Vespucio la ciudad de Venecia —Venezia, en italiano—, según lo manifestó en una carta a Piero de Médici. Fue éste un motivo que inspiró a Ojeda a dar el nombre de Venezziola o Venezuela —Pequeña Venecia— a la región y al golfo en que habían hecho el descubrimiento, recibiendo la denominación de golfo de Venezuela. El nombre acuñado por el explorador envolvería luego a todo el territorio.3 Con posterioridad la región también fue conocida como Tierra Firme, por ser la primera región no insular del continente en ser explorada por los europeos.
