In vorgeschichtlicher Zeit wurde das Gebiet von Arawakindianern besiedelt.
Am 25. März 1555 gründete der spanische Kapitän Alonso Díaz Moreno die Stadt als erste spanische Siedlung im Zentrum Venezuelas. Der offizielle Name lautete "Nuestra Señora de la Asunción de Nueva Valencia del Rey".
Der berüchtigte Konquistador Aguirre belagerte die Stadt 1561. Im Jahre 1677 wurde sie von französischen Piraten überfallen, wobei die Innenstadt niederbrannte und viele wichtige Dokumente über Venezuelas frühe Besiedlung vernichtet wurden.
Der deutsche Forschungsreisende Alexander von Humboldt besuchte Valencia auf seiner Reise durch Südamerika und berichtete von sechs- bis siebentausend Einwohnern.
Seit der Inbesitznahme durch die Spanier war Venezuela spanische Kolonie. Im Jahre 1811 wurde Valencia zur Hauptstadt der ersten Republik Venezuelas erklärt. 1813 wurde die Stadt von Boves umzingelt und nach einer langen Schlacht besetzt. Die Männer wurden massenhaft hingerichtet, die meisten Frauen vergewaltigt.