Vitoria wurde von Sancho VI. el Sabio, König von Navarra, im Jahr 1181 mit dem Namen Nueva Victoria (deutsch „neuer Sieg“) als Erweiterung der baskischen Siedlung Gasteiz und als Befestigungsanlage gegen Kastilien gegründet. Die auf einem Hügel inmitten der alavesischen Hochebene gelegene Siedlung Gasteiz ist noch heute als Altstadt das Herz von Vitoria.
Im Laufe der Geschichte wechselte Vitoria von Navarra nach Kastilien. Im Jahr 1431 wurde Vitoria von Johann II. von Kastilien das Stadtrecht verliehen.
Am 21. Juni 1813 siegte Wellington über Joseph Bonaparte in der Schlacht von Vitoria, was für die Franzosen eine schwere Niederlage während der Koalitionskriege bedeutete.
Seit 1980 ist Vitoria-Gasteiz die Hauptstadt der spanischen Autonomieregion Baskenland. Die Wahl von Vitoria wurde damals bewusst vorgenommen, um Álava, das zwischen spanischer und baskischer Loyalität schwankte, stärker an das Baskenland zu binden. Seit Vitoria Hauptstadt des Baskenlandes ist, hat die Stadt viele neue Einwohner angezogen, darunter oft Beamte der baskischen Regierung.