Després de la crisi de l'Imperi Romà, arribaren a la zona on s'assenta Vitòria diverses tribus del nord d'Europa. En aquest context, el lloc va restar en una zona marginal entre els visigots (al sud) i els francs (al nord).

Tradicionalment s'ha afirmat que la ciutat anomenada Victoriacum, que fou fundada pel rei visigot Leovigild l'any 581, correspon a Vitòria.[1] Aquesta afirmació es basa en el següent text:[2]

No obstant això, aquesta dada no està suficientment provada i experts historiadors opinen que Victoriacum no estava en l'actual Vitòria o antiga Gasteiz sinó en una zona propera, probablement als peus del Gorbeia on hi ha un poble anomenat Vitoriano al municipi alabès de Zuia. A. Barbero i M. Vigil opinen que també va poder tractar-se de l'oppidum d'Iruña, la Veleia de Ptolemeu, complex romà de gran importància situat en terres alabeses, a 11 km de Vitòria.

Treballs arqueològics realitzats recentment a la ciutat apunten a la presència de francs, i no visigots, a la zona, dificultant la identificació de Victoriacum com Vitòria. No existeixen moltes restes arqueològiques d'aquesta època, però sembla que va haver-hi assentaments francs permanents a la rodalia de l'actual ciutat. Per exemple, en el jaciment d'Aldaieta (Nanclares de Gamboa) s'han trobat tombes adornades seguint els costums francs. Es creu que aquest assentament data entre els segles vi i viii. De la mateixa manera, els objectes oposats en les excavacions realitzades sota la catedral de Santa María de Vitòria semblen ser d'aquesta cultura. És més, després d'examinar les característiques d'aquests objectes es pot afirmar que són del segle VIII o posteriors.[3]

De qualsevol manera, no sembla que la influència, sigui visigoda o franca, fos important a la zona de Vitòria. Segons mostra la reja de San Millán de la Cogolla, en el segle xi la majoria de topònims de la Planada Alavesa, on es troba Vitòria, eren d'origen basc incloent alguns altres d'origen romanç.[4] La reixa de San Millán és un document de l'any 1025 que llista una sèrie de poblacions que pagaven delmes al monestir de San Millán. El primer esment documentat d'un llogaret denominat Gastehiz es troba en aquest document, encara que no se cita la localització d'aquest llogaret. Aquest mateix document esmenta igualment moltes de les poblacions que componen actualment el municipi de Vitòria.

L'actual Vitòria va ser fundada pel rei navarrès Sanç VI el Savi l'any 1181 en el lloc de Gasteiz («...novum nomen imposui scilicet Victoria quae antea vocabatur Gasteiz...» / «...a la que vaig imposar el nou nom de Vitoria que abans s'anomenava Gasteiz») amb la denominació de Nova Victoria. L'origen de la fundació fou, de la mateixa manera que en altres ciutats de la zona (Antoñana, Bernedo, Lapuebla de Arganzón, Laguardia), la necessitat per part del rei navarrès de crear una línia defensiva contra el regne de Castella.[5]

Segons estudis recents,[6] el poblat de Gasteiz comptava amb una muralla defensiva cent anys abans de la fundació de Victoria per Sanç VI.

Aquesta muralla va ser anys més tard decisiva en el setge de vuit mesos amb el qual les tropes del rei Alfons VIII van poder prendre el control de la ciutat. De tal manera que l'any 1200 pas ja a dependre de Castella.

El mateix rei castellà la va dotar del seu primer eixample gòtic en el vessant oest. Alfons X el Savi la va estendre en 1256 cap a l'est amb nous carrers gremials. Enric III, en 1399, concedeix a la ciutat dues fires franques.

Va ser important el seu call, abans de l'expulsió dels hebreus ordenada pels Reis Catòlics: el vell cementiri jueu encara es conserva en forma de parc (Judizmendi) amb un monument commemoratiu del seu passat. En 1431, el rei Joan II de Castella li va atorgar el títol de ciutat. En 1463 va ser una de les cinc viles fundadores de la Germandat d'Àlaba juntament amb Sajazarra, Miranda de Ebro, Pancorbo i Salvatierra. En 1466 Enric IV de Castella va concedir a la ciutat el títol de lleial i en 1470 Ferran el Catòlic la nomenà molt lleial.

El 22 de setembre de 1483 Isabel I jura els furs i privilegis de la ciutat al Portal d'Arriaga.

Controvèrsia arqueològica-històrica: Els estudis arqueològics sobre una petita superfície a l'interior de la catedral han donat amb una anàlisi del C14 (datació amb Carboni 14) que situa la construcció de la muralla a de finals del segle xi (cent anys abans de la fundació de la vila pel rei navarrès Sanç el Savi), no obstant això, molts historiadors experts en Furs medievals no recolzen aquesta tesi. Els furs atorgats pels reis, o estament jurídic, permetia la construcció de muralles i guarnició però no podia existir un recinte de 20 torres com interpreten el seu cèrcol emmurallat, sense el consentiment reial en forma jurídica. Vitòria-Gasteiz va ser creada com a tinença defensiva juntament amb Zaitegi (1187), amb la finalitat de protegir la nova frontera que s'havia creat després del tractat amb Castella de 1179. L'existència d'algun tram de muralla anterior només pot ser defensat des del punt de vista arqueològic però manca de fonament històric.

El 22 de gener de 1522, va arribar a Vitòria la notícia que Adrià d'Utrecht, que es trobava en aquest moment a la ciutat allotjat en la Casa del Cordón, havia estat triat nou Papa 13 dies abans. El futur Adrià VI romandria a la capital alabesa poc més d'un mes, exercint com regent d'Espanya i preparant Navarra per a la defensa enfront de la invasió francesa.

En 1615, amb motiu de les noces reals, es van allotjar a la ciutat Anna d'Àustria, reina de França, i Isabel de Borbó, esposa del futur Felip IV.

Durant la guerra del Rosselló, Vitòria, així com gran part del País Basc, va ser ocupada per un curt període per les tropes franceses, les quals van avançar fins a Miranda de Ebro. Aquesta ocupació va concloure amb la Pau de Basilea que va posar fi al conflicte.

El 13 d'abril de 1808, Ferran VII d'Espanya es va allotjar a la Casa Consistorial mentre es dirigia a Baiona, on tindrien lloc les famoses abdicacions. A l'alba del 19 d'abril, una immensa gentada omplia l'actual carrer Mateo de Moraza per impedir aquest viatge, arribant a tallar els tirants del carruatge, per la qual cosa va haver de partir de Vitòria precedit de la cavalleria francesa.

Entre el 5 i 9 de novembre, Napoleó Bonaparte va pernoctar a la casa Etxezarra de la capital alabesa en el seu camí cap a Madrid per col·locar al seu germà, Josep, en el tron d'Espanya. Josep havia fet del palau de Montehermoso el seu palau reial particular durant la retirada precedent després de la derrota en Bailén.

Entre els esdeveniments històrics més destacats està el d'haver estat escenari de la Batalla de Vitòria el 21 de juny de 1813, en la qual les tropes franceses, movent-se en retirada, van ser derrotades pel Duc de Wellington al costat de l'alabès General Álava. Com a resultat de la contesa, Josep Bonaparte fugí perdent gairebé tot el botí robat. Amb aquesta batalla es va posar fi pràcticament a la Guerra del Francès. Hi ha un monument a aquesta batalla a la plaça principal de la ciutat (la Plaza de la Virgen Blanca), conegut com el Monument a la Independència.
Quan a la fi de juliol del mateix any va arribar la notícia a Viena, Johann Nepomuk Mälzel va encarregar Ludwig van Beethoven la composició d'una simfonia amb motiu d'aquest fet. Es tracta del op. 91 Wellingtons Sieg o *Die Schlacht bei Vitòria o Siegessymphonie.

En 1843, va arribar l'autorització per construir l'Institut d'Ensenyament Mitjà, seu actual del Parlament Basc i anteriorment el convent de Santa Clara. L'any acadèmic de 1853-1854 van començar les classes culminant així un vell somni de la ciutat. El vell Institut d'Ensenyament Mitjà va ser testimoni de bona part de la vida cultural d'aquesta ciutat. Cal recordar, entre altres coses, la Universitat Lliure, creada arran de la revolució de 1868. Aquesta Universitat va funcionar a partir de 1869, truncant-se abans de començar el curs 1873–1874, en gran part per culpa de la segona guerra carlista. Cal recordar els noms de Ricardo Becerro de Bengoa, Julián Apraiz, Federico Baraibar Zumárraga, etc. Aquest últim (1851–1918) fou un gran hel·lenista i un dels primers que va impartir-hi classes extraescolars de basc a Vitòria.

La riquesa cultural i educativa durant la segona meitat del segle xix li va valer a Vitòria l'apel·latiu d'Atenes del Nord.[7]

De començaments de segle i fins a la dècada dels 50, Vitòria és una petita ciutat, amb poca indústria i molt conservadora, la qual cosa explica els relativament pocs incidents en la guerra civil llevat l'afusellament del seu alcalde republicà Teodoro González de Zárate.

A partir de la dècada de 1950, a la ciutat es va iniciar una forta industrialització que produiria una transformació de la ciutat en tots els aspectes, sobretot els demogràfics i socials, passant a ser d'una petita ciutat de serveis i administració a una ciutat industrial que va batre rècords de creixement demogràfic relatiu en tot l'Estat, en els anys 60, amb un percentatge més gran del 40%. Així, de la dècada dels 60 als 70 gairebé va duplicar la seva població, per la gran quantitat de treballadors immigrants rebuts.

La ciutat de Vitòria, antany caracteritzada per les seves tradicions conservadores, va canviar, donant-s'hi els episodis més dramàtics de la Transició Espanyola. Com els esdevinguts a l'Església de San Francisco de Asís, al barri de Zaramaga, que va ser escenari el 3 de març de 1976 de la massacre del 3 de març, on la policia va disparar contra una assemblea de treballadors. El desallotjament de l'església en la qual se celebrava una assemblea va acabar amb l'ametrallament dels assemblearis per part de la policia, la qual cosa va causar la mort de 5 civils pels trets i ferides de bala a més d'un centenar.

El 20 de maig de 1980, Vitòria es va convertir en capital oficiosa (és a dir, a efectes administratius, i de forma no oficial) de la Comunitat Autònoma del País Basc per decisió del Parlament Basc, que així ho va acordar per mitjà de la seva Llei de Seus. Així, Vitòria és capital de la província d'Àlaba i de la Comunitat Autònoma Basca i seu de la Diputació Foral d'Àlaba,de les Juntes Generals d'Àlaba, del Govern Basc i del Parlament Basc.

Avui Vitòria és Capital Verda Europea [8] (European Green Capital).