New Andalusia (in Spanish, Nuevo Andalucía) was a Spanish viceroyalty in the 1500s. It was comprised of what is now eastern Venezuela, western Guyana and far north Brazil.