| Native Name: | Tierra Firme |
| Conventional Long Name: | Governorate of New Andalusia (and Coquivacoa) |
| Common Name: | New Andalusia |
| Status: | Governorate of Castile (Spanish Empire) |
| Empire: | Spain |
| Religion: | Roman Catholicism |
| Era: | Spanish Empire |
| Year Start: | 1501 |
| Year End: | 1513 |
| Event End: | Creation the Great Governorate of Castilla de Oro. |
| P1: | Province of Tierra Firme |
| S1: | Castilla de Oro |
| Flag Alt: | Banner of Castille under the Hubsbourg |
| Image Map Caption: | Tierra Firme: Castilla de Oro and New Andalucia (with Coquivacoa) |
| Flag P1: | Banner of arms crown of Castille Habsbourg style.svg |
| Flag S1: | Banner of arms crown of Castille Habsbourg style.svg |
| Capital: | Santa Cruz |
| Government Type: | Monarchy |
| Title Leader: | List of Castilian monarchs |
| Leader1: | Joanna of Castile, Ferdinand the Catholic |
| Representative1: | Alonso de Ojeda |
| Common Languages: | Spanish |
The Governorate of New Andalusia (Spanish; Castilian: Gobernación de Nueva Andalucía, pronounced as /es/) 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). This was territory originally seen by Christopher Columbus.
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. The settlements were later abandoned for new explorations.
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.
The Governorate of New Andalusia territories were further unified in May 1513 with the Governorate of Castilla de Oro.