En los años centrales del reinado de Alfonso II, el Casto (791-842) se aborda la construcción de este templo, a unos 800 m. del núcleo de la capital ovetense, en las proximidades de un complejo palacial, cuyos vestigios arqueológicos aún no han sido localizados. Asi aparece mencionado en la Crónica Rotense (883) y, de forma más precisa, en la Crónica ad Sebastianum (hacia 885): “Edificó también al Norte, distante del palacio casi un estadio, una iglesia en memoria de san Julián Mártir, poniendo alrededor, aquí y allá, dos altares decorados con admirable ornato”. El rey Alfonso III lo donará años más tarde a San Salvador de Oviedo. Es más conocido como Santullano, apócope de Sanctus Julianus, porque fue consagrado bajo la advocación de los santos esposos de origen egipcio, Julián y Basilisa.
San Julián es el mayor de los templos prerrománicos asturianos, de planta basilical con transepto, único en Asturias, siendo también excepcional en su arquitectura. Cuenta con tres naves cortas y anchas, separadas por arcos de medio punto sobre pilares, delimitados por un arco toral que remarca el ingreso a la nave transversal. Ese transepto continuo, inscrito en la planta del edificio, precede a la cabecera, que está provista de tres capillas abovedadas sin comunicación interna que, al exterior, se alojan en un muro testero recto.
Se usaron en su construcción caliza y arenisca en los muros y elementos pétreos; mármol para algunas piezas de tradición visigoda en la capilla central; ladrillo para el desarrollo de los arcos de medio punto y arcos de descarga proyectados sobre puertas y ventanas; madera para las armaduras a dos aguas en naces, transepto y pórtico de entrada. Se conservan algunas vigas grabadas con dibujos geométricos. Y finalmente, el estuco calizo, que se empleó para realizar la celosía de la capilla norte, la única original que pervive. De ello podemos deducir que se realizaron originalmente todas las demás del mismo modo.
La sobriedad de la talla escultórica se ve compensada por la extensísima muestra pictórica que aún perdura en los muros. Es el repertorio más representativo y mejor conservado de toda la Edad Media Hispana. Elaborado al fresco, se puede apreciar el trazado previo basado en una sencillas técnica de incisiones, que se realizan sobre el enlucido tierno.
Su programa iconográfico es enigmático y fascinante. Está dividido en tres niveles jerárquicos según los modelos bizantinos y su estilismo es heredero de la pintura mural de los estilos II y IV pompeyanos.
El de abajo más austero, con imitaciones marmóreas de estriados en color rojo, imitan columnas y acanaladuras. En los intradoses de las columnas, guirnaldas que imitan espigas, que surgen de vasos gallonados, sobre un fondo amarillo oro. La parte central imita a una cornisa policromada, que recorre el perímetro de la iglesia y sobre ella, un registro de marcos arquitectónicos con variados edificios, separados por columnas de capitel corintio y pilastras estriadas y enmarcados por cortinas simuladas, recogidas a ambos lados, para dejar ver las edificaciones, a veces repetidas. Todos tienen puertas y ventanas, abiertas o cerradas y en una perspectiva a 45º
El nivel superior también cuenta con representaciones de edificios palaciales, con múltiples detalles y colores intensos. Los arcos, con óvalos que imitan piedras preciosas de colores, están presididos por cuatro cruces gemadas, que corresponden al patrón de cruz latina, conocido como Cruz de la Anástasis, la Vera Cruz y que carecen de pié; están apoyados sobre dos columnas que imitan acanaladuras y el típico sogueado.
Destaca el Crucificado, conocido como Cristo del Consuelo, que preside el ábside central. Es una talla de madera policromada y dorada del S. XIII, con rasgos románicos y atributos góticos.
A lo largo del S. XII se realiza la primera restauración en la cubierta, pero será en los S. XVII-XVIII cuando se construyan unas bóvedas tabicadas en la nave central y transepto, mejorando el pavimento. En el S. XX (1912-16), D. Fortunato de Selgas y Vicente Lampérez promueven una profunda restauración y se descubren entonces las maravillosas pinturas murales y restauradas en los años 1970-80. Desde 1917 la iglesia es monumento nacional.