Über den Ursprung des Names „Venezuela“ gibt es zwei Theorien: Manche schreiben ihn Amerigo Vespucci zu, der zusammen mit Alonso de Ojeda 1499 eine Expedition entlang der nordwestlichen Küste führte (heute bekannt als der Golf von Venezuela). Als sie die Guajira-Halbinsel erreichten, beobachtete die Mannschaft die Pfahlbauten (palafitos), die die Eingeborenen Añu über dem Wasser errichtet hatten. Diese erinnerten Vespucci an die Stadt Venedig und infolgedessen wurde die Region Venezuela genannt, was soviel wie „Klein-Venedig“ bedeutet.
Andererseits sagt der spanische Conquistador und Geograph Martín Fernández de Enciso, Mitglied der gleichen Mannschaft, in seiner Schrift „Summa de Geografía“, dass die Bevölkerung dieser Region einen flachen Felsen bevölkerte und „Veneciuela“ genannt wurde.