La Gobernación de Nueva Andalucía ( español : Gobernación de Nueva Andalucía , pronunciado [ɡoβeɾnaˈθjon de ˈnweβa andaluˈθi.a] ) fue una entidad colonial española en lo que hoy constituye los territorios costeros del Caribe de América Central, Colombia y Venezuela, y las islas de lo que hoy son Jamaica, Cuba, Haití, República Dominicana y Puerto Rico. El Gobierno de Nueva Andalucía se estableció en Venezuela desde 1501 hasta 1513.
En 1501, Alonso de Ojeda colonizó el territorio continental de la actual Venezuela, y recibió la Gobernación de Nueva Andalucía ( Coquivacoa ), entre el Cabo de la Vela y la Isla Margarita . Este fue un territorio visto originalmente por Cristóbal Colón .
El 3 de mayo de 1502 Ojeda fundó el pueblo de Santa Cruz en la Península de la Guajira , primera colonia española en la futura Provincia de Tierra Firme . Posteriormente, los asentamientos fueron abandonados para nuevas exploraciones.
En 1509 se concedió autoridad a Alonso de Ojeda para colonizar los territorios comprendidos entre el Cabo de la Vela y el Golfo de Urabá como parte de la Gobernación de Nueva Andalucía.
Los territorios de la Gobernación de Nueva Andalucía se unificaron aún más en mayo de 1513 con la Gobernación de Castilla de Oro .