The Governorate of New Andalusia (Spanish: Gobernación de Nueva Andalucía, pronounced [ɡoβeɾnaˈθjon de ˈnweβa andaluˈθi.a]) was a Spanish colonial entity in what today constitutes the Caribbean coastal territories from Central America, Colombia and Venezuela, and the islands of what today are Jamaica, Cuba, Haiti, Dominican Republic and Puerto Rico.

The Government of Nueva Andalucia was set in Venezuela from 1501 to 1513.

In 1501, Alonso de Ojeda colonized the mainland of present-day Venezuela, and received the Governorate of New Andalusia (Coquivacoa), between Cabo de la Vela and Isla Margarita (island).

On May 3, 1502 Ojeda founded the town of Santa Cruz in the Guajira Peninsula, the first Spanish colony in the future Province of Tierra Firme.

In 1509, authority was granted to Alonso de Ojeda to colonize the territories between Cabo de la Vela and the Gulf of Urabá as part of the Governorate of New Andalusia.