El templo se construyó en dos fases. La parte más importante se llevó a cabo entre 1907 y 1914. De esta primera época son la cripta, consagrada en 1911, la cabecera y la parte inferior de la nave. La falta de recursos económicos fue un problema presente desde el inicio de la obra y la razón de muchos problemas. El presupuesto fue superado al poco tiempo de comenzar la obra por el encarecimiento de los materiales y el transporte, los contratistas no podían entregar ni cobrar el trabajo, los trabajadores no percibían su jornal, etc. hasta que en 1914 se paralizaron las obras. A pesar de que la cabecera estaba casi terminada, las naves quedaron construidas hasta ocho metros aproximadamente.
Tras un parón de 32 años, la segunda fase de construcción comenzó en 1946 bajo la responsabilidad del arquitecto Miguel Apraiz,hijo de Julián Apraiz. También durante esa fase estuvieron presentes los problemas económicos y fue necesario introducir importantes modificaciones del proyecto: se quitaron las dos altas torres con chapitel de la fachada, el cimborrio y casi todos los elementos escultóricos. Además emplearon el hormigón armado y piedra artificial como material de construcción. Todos estos cambios ocasionaron desproporciones estéticas en la ya anacrónica construcción, debido a que le restaron la característica verticalidad del neogótico. La catedral se consagró en 1969 y en 1973 se dieron por terminadas las obras. A pesar de todo, aún hoy son visibles las partes inacabadas.
El templo tiene planta de cruz latina con una amplia cabecera y una girola de siete capillas, a la manera de las grandes catedrales góticas europeas. Tiene cinco naves de gran altura cubiertas por bóvedas de crucería simple. La techumbre se sostiene sobre grandes pilares con columnillas adosadas. Un triforio recorre todo el perímetro interior del edificio emulando el estilo gótico. Gracias a los grandes y largos ventanales que iluminan el interior el templo se caracteriza por tener una espacialidad limpia y diáfana.
Todo el edificio alberga una extraordinaria labor de escultura, realizada en la primera fase. Los elementos arquitectónicos de la cripta y el exterior de la cabecera están llenos de esculturas de buena calidad. La mayoría está ejecutada en un estilo académico y representa temática religiosa, como corresponde con el edificio. Sin embargo destacan mucho las esculturas de temática vegetal y animal, así como los de temas profanos, como los que muestran escenas de la construcción de la catedral: en muchos relieves podemos encontrar retratos y caricaturas de escultores y canteros que trabajaron en el catedral, como Lorenzo Fernández de Viana, Moisés Huerta y otros. Una gárgola es también un retrato de Pedro Galdós -el que fue contable de la Catedral- y del fotógrafo Enrique Guinea. Estos protagonistas y testigos de la Catedral están realizados en un estilo libre y expresivo, y aportan frescura y una importante riqueza artística.
En la segunda fase trabajaron los hermanos Aurelio y Manuel Rivas de cuya gubia han salido las gárgolas de las naves laterales, varios escudos interiores (con modelos de Lorenzo Fernández de Viana) y las esculturas de la fachada principal. Las tallas de los Rivas son más geométricas que las de la primera fase, de menos calidad artística, y también desarrollan temas contemporáneos, como se observa en varias gárgolas con varios personajes de la Guerra Civil española de clara lectura política.
La cripta es la parte que ostenta la mayor valía artística. A la manera de las catedrales góticas fue creada como panteón de obispos, pero a pesar de haberse diseñado y modelado los sepulcros nunca se llegaron a tallar ni se inhumó a ningún obispo. Los trabajos de escultura de la cripta son extraordinarios, y por haberse realizado en su totalidad en la primera fase, mantiene una unidad estética: la arquitectura, escultura y vidrieras de colores están perfectamente integradas.
Otros elementos destacados de esta catedral son las vidrieras, elementos que no pueden faltar en una iglesia neogótica para continuar con la tradición gótica de la mística de la luz. La cabecera está iluminada con vitrales de la Casa Maumejean realizados entre 1907 y 1909 en Madrid. Maumejean es el taller vidriero más importante del siglo XX y sus obras de Vitoria, todas hechas en vidrio coloreado y emplomado, son vistosas y de gran calidad. En las capillas de la girola, que son las capillas de Álava, Gipuzkoa, Bizkaia y Navarra, se representan sus patrones y santos de su devoción, y en otras capillas están los retratos de los papas Pío IX, Pío XII, Juan XXIII y Pablo VI. En la cripta se narran escenas bíblicas referidas a la muerte y la Resurrección, acorde con la función funeraria de este espacio. En las naves se colocaron una sencillas vidrieras de motivos geométricos y escudos de los obispos de la Diócesis. Finalmente, las vidrieras del presbiterio son de la segunda fase y están realizadas en la casa Vidrieras de Arte de Bilbao en 1954.
La Catedral Nueva de Vitoria es una de las obras neogóticas más importantes que se construyeron en el País Vasco a principios del siglo XX. Fue un punto de encuentro importante de escultores y a través de él los artistas catalanes introdujeron el modernismo en Álava. Estos escultores trabajaron en la Escuela Práctica de Modelado y Talla fundada en 1909 y a través de la formación de nuevos artistas se difundió el nuevo estilo. En cuanto a la historia social hay que reconocer el valor de las reivindicaciones laborales y huelgas organizadas por los canteros y escultores de esta catedral, que fueron los introductores de las ideas anarquistas y socialistas en la sociedad alavesa.
Desde 1999 la Catedral alberga en su girola el Museo Diocesano de Arte Sacro. Las celebraciones litúrgicas se celebran en la cripta.