La iglesia de San Millán adquiere su advocación de la tradición que sitúa en Berdejo el lugar de nacimiento de este eremita, en el año 473. El templo se encuentra encaramado en lo alto del pueblo, sobre un poderoso peñasco cortado a pico en parte de su perímetro, que le confería una ventajosa capacidad de defensa frente a posibles enemigos en otros tiempos más agitados. El origen de la fábrica es románico, aunque las remodelaciones y reparaciones sufridas a lo largo de los siglos hacen que sólo se manifieste con claridad en este estilo la cabecera, e incluso en ella veamos añadidos. La nave fue continuada con soluciones semejantes, tiene los arcos apuntados, fue levantada con toda probabilidad ya bajo formas góticas y con el paso del tiempo las sucesivas reformas desvirtuaron su aspecto original. En el siglo XVII quedó convertida en barroca y se le añadieron varias capillas a sus lados. Durante el año 2006 el edificio fue sometido a las últimas obras de rehabilitación, de las cuales resta concluir las que competen al interior del edificio. Su planta consta de una nave de 27,70 m de longitud, dividida en tramos por tres arcos transversales. La distancia entre las pilastras que los sostienen es de 7,20 m. Sobre ellos una cubierta metálica a dos aguas sustituye a la bóveda de lunetos de sección apuntada que describía Abbad, a mediados del siglo xx, quien apuntaba la posibilidad de que la iglesia hubiese sido acabada en estilo gótico para, más tarde, ser transformada bajo estética barroca. El material utilizado en ábside, presbiterio y parte de la nave fue la piedra sillar, mientras que el resto de muros son de mampostería. En muchos de los sillares exteriores, y en alguno de los interiores, se aprecian marcas de cantería que repiten un sencillo trazo recto en el que incide otro oblicuo más corto. Además de estas marcas, en un sillar de la parte baja del muro norte del presbiterio, aparece una cruz latina con sus cuatro extremos rematados en triángulos; vemos esparcidas cruces más sencillas. El exterior del ábside, semicilíndrico, queda dividido en cinco paños por cuatro semicolumnas edificadas con tambores y adosadas a su alzado, que se elevan hasta la cubierta, terminando en sencillos capiteles que sostienen la cornisa junto a canecillos de perfil liso. El deteriorado estado de estos capiteles tan sólo deja distinguir una decoración a base de bolas en la parte superior de sus ángulos. En el segmento central abría un vano de medio punto, abocinado hacia el interior, que hoy en día se encuentra cegado. De él solamente pervive su proyección interna, ya que al exterior está destruido. Los restantes vanos, entre ellos la habitual ventana meridional de iluminación del retablo, no son originales. Hay que señalar la existencia de una hornacina de medio punto en la parte sur de la cabecera, emplazada en el lugar donde habitualmente hay ventanas en templos románicos. El interior del cilindro absidal, de 6,75 m de anchura, se cubre con una bóveda de cuarto de esfera realizada en yesería, con decoración geométrica, que impide averiguar si el aparejo original permanece tras ella. Lo mismo ocurre en el presbiterio, donde se prolonga dicha decoración de escayola ocultando, probablemente, la bóveda de medio cañón románica. Los muros de la cabecera muestran refecciones en varios lugares y vestigios de una moldura horizontal original sobre la ventana. El arco de embocadura está rehecho. La nave continuaba las mismas fórmulas sencillas. En el muro norte se aprecia nítidamente un corte de fábrica entre la cabecera y el muro septentrional, pero de él no es posible deducir cuánto tiempo estuvo interrumpida la obra, dado que prosiguió con pautas semejantes en lo que corresponde al aparejo, algo más irregular, y al remate (canecillos y cornisa). Pasada la torre, todavía queda una estrecha banda de aparejo similar al del otro lado, que se prolonga en otro más descuidado lleno de remiendos, para concluir en una fábrica más tardía de mampostería, en la que se abrió la puerta occidental. Por el interior, se ven dos arcos transversales de piedra de tosca ejecución (probablemente también parcialmente remodelados a lo largo de los siglos). Prefieren el diseño apuntado sobre pilastras sin molduración. No son todos los que se proyectaron. Advertimos la utilización de una tipología habitual en el tardorrománico zaragozano, consistente en la perduración de bóvedas de horno y arcos de medio punto en la cabecera, combinados con arcos apuntados sobre pilastras sin impostas ni ornamentación en la nave. Amplias capillas anejas, refuerzos en la base de los muros y otras edificaciones anejas ocultan la fábrica por el exterior, mientras que en el interior se advierten añadidos tan evidentes como el tramo occidental, que desvirtúan la edificación medieval. A pesar de que los testimonios románicos de carácter rural suelen ser de difícil datación, debido a que presentan, en términos generales, un aspecto arcaizante frente a otros de mayor prestancia (que pueden pertenecer a las mismas o anteriores fechas), las características descritas en los restos tardorrománicos de la iglesia de San Millán de Berdejo, y especialmente el formato de los canecillos, permiten remontar el origen de su fábrica a los últimos años del siglo XII o a la primera mitad del siglo XIII.