C'est l'un des plus anciens diocèses d'Espagne ; sans compter les traditions anciennes parlant de la fondation par saint Jacques le Majeur ou les fausses chroniques inventées au XVIIe siècle qui mentionnent saint Ephrem et d'autres évêques légendaires. Le 1er évêque dont on possède des preuves documentées est Basilide(es), évêque libellatique lors des persécutions ordonnées par Dèce, ce qui a nécessité l'intervention de Cyprien de Carthage et du pape Étienne Ier. Sabin, 2e évêque, siège pendant les répressions de Valérien, il est contemporain de sainte Marthe, vierge et martyre en 251, actuellement patronne de la ville d'Astorga. Le diocèse est également représenté au concile d'Elvire, le premier célébré par l'Église chrétienne en Hispanie dans le contexte des persécutions de Dioclétien. Saint Toribio, dans sa correspondance avec Hydace de Chaves, mentionne la présence de priscillianistes dans son diocèse et fut témoin de la conversion du royaume suève de Rémismond à l'arianisme. Ce même évêque restaure les temples détruits par Théodoric II et rapporte de Jérusalem un fragment de la Vraie Croix maintenant vénérée dans le monastère de Santo Toribio de Liébana.
Les documents du diocèse sont perdus après l'évêque Aurelio (693). En 711 a lieu l'invasion musulmane et peu après commence la Reconquista et l'expansion du royaume des Asturies. Astorga est reconquis sous le règne d' Alphonse Ier et le diocèse est certainement restauré en 747 bien que sa repopulation n'ait commencé que 100 ans plus tard sous le règne de Ramire Ier (842-850).