Se trata del obispado más antiguo conocido en las actuales tierras de Álava. Es en la Crónica Albeldense donde aparece una nómina de obispos de época de Alfonso III, concretamente en el 881, y entre ellos se cita al obispo Álvaro de Velegia (Alvarus Velegiae).
Veleia es una antigua ciudad romana cuyo yacimiento se encuentra en Trespuentes (municipio de Iruña de Oca), a unos 9 kilómetros al este de Vitoria. Velegia había sido sede, según la Notitia Dignitatum, de una cohorte romana (Cohors I Gallica). Además controlaba la vía Asturica-Burdigala antes de los estratégicos desfiladeros de Pancorbo y las Conchas de Arganzón. Su importancia se mantuvo hasta siglos después, pues es mencionada por la Crónica Ad Sebastianum de Alfonso III (Uelegia Alabense) como una de las ciudades atacadas por Alfonso I y su hermano Fruela tras la descomposición del poder andalusí en la Meseta Norte con las rebeliones bereberes del 741.
Hoy en día se conserva la que supuestamente es su lápida sepulcral. Se hallaba en la parte exterior
de la iglesia de Bolívar (un pueblo a 8 km. de Vitoria), y actualmente está en el arco románico de la misma iglesia, instalado en los jardines del antiguo Seminario Conciliar de Vitoria. Las medidas de la piedra son 0,61 X 0,30 m., y la inscripción, repartida en cuatro líneas, dice:
OBIIT ALVARO EPSCPVS XIII KLS NBRS E DCCCC [L o X]XVI
Esta claro que dice que murió Álvaro el obispo, pero sobre la fecha no existe unanimidad en su transcripción, pues unos leen 926 y 966. Por lo tanto la fecha de la muerte sería el 20 de octubre del año 888 o 928.
La lápida ha sufrido numerosas manipulaciones y en la actualidad aparece falseada. Es interesante consultar el artículo de Juan Carlos Elorza, De Epigrafía cristiana alavesa, Estudios de Arqueología Alavesa, Tomo IV, Diputación Foral de Álava, Vitoria, 1970. Presenta todos los facsímiles existentes de la lápida desde el siglo XIX.
Algunos autores como Alberto González de Langarica han supuesto que este obispado sería el de numerosos obispos que aparecen desde el siglo VIII en la zona aunque sin sede y propone este episcopologio: Valentín (759), Pascasio (811), Kintila (812), Leolalio (832), Antonio (863), Seruato (867) Placentio (872) y Álvaro de Velegia (877-888).