"Nova Andaluzia" y Paria en un mapa español de 1562

La provincia de Venezuela y la parte austral de Nueva Andalucía. Mapa de 1635

La Provincia de Nueva Andalucía, más tarde llamada Provincia de Cumaná, fue una provincia creada en la zona oriental de la actual República Bolivariana de Venezuela que reunió a las anteriores provincias o gobernaciones de Nueva Andalucía (creada en 1536) y Paria, en una única entidad creada el 27 de mayo de 1568 con Diego Hernández de Serpa como primer gobernador.

La provincia incluía territorios de los actuales estados Sucre, Anzoátegui y Monagas. Sus ciudades más importantes fueron Cumaná (capital provincial) y Nueva Barcelona.

En 1633 Juan de Orpín estableció la gobernación de Nueva Cataluña con partes de las gobernaciones de Venezuela y de Nueva Andalucía, entre el cabo Codera, el actual pueblo de Cariaco y el río Orinoco, fundando Barcelona el 12 de febrero de 1638. En 1654 Nueva Cataluña o gobernación de Barcelona, se integró a Nueva Andalucía. Hacia 1726 estaba integrada por los territorios de Cumaná, Guayana, Barcelona, Maturín y la isla de Trinidad. Hasta 1739 dependió de la Real Audiencia de Santo Domingo y hasta 1777 de la Real Audiencia de Santa Fe de Bogotá. Justamente en este último año se constituye integramente a lo que históricamente se conoce como la Capitanía General de Venezuela, junto con las provincias de Barinas, Trinidad, Margarita, Venezuela o de Caracas, Mérida-Maracaibo y de Guayana. A partir del 5 de julio de 1811 declararía su Independencia.

Con el paso de los años duarante la Colonia y el desarrollo de la provincia, los territorios de Guayana, Trinidad se constituyeron en provincias independientes de la de Cumaná.