Templo construido a partir del año 1080 por Raimundo de Borgoña. Ubicada en el conocido como Arrabal Mayor, un barrio que durante la edad media estaba ocupado por tejedores y moriscos.  De esta edificación sólo nos ha llegado la torre. Hacia el año 1111 Alfonso I el Batallador, rey de Aragón y también de Castilla, gracias a su matrimonio con doña Urraca. Este matrimonio fue clave en la definición de la planta del nuevo templo, por que Alfonso I quiso que fuera una réplica de la Catedral de Jaca. Así pues, San Millán nos sorprende por ser una "iglesia aragonesa" en medio de Castilla.

Tiene planta basilical formada por tres naves divididas en cinco tramos. También tiene transepto, que sobresale en alzado, pero no en planta,  en el que originariamente se abrían tres ábsides. Posteriormente todavía se añadió un ábside más por el lado norte.

En la intersección entre la nave principal y el transepto se levanta una cúpula sobre trompas. En este caso está reforzada por dos pares de arcos que en cruzarse forman un cuadrado.

Las naves, como en Jaca, están separadas por arcos formeros de medio punto que se apoyan de forma alternada en columnas adosadas al pilares cruciformes y en grandes columnas cilíndricas. Tanto unas como las otras tienen grandes capiteles decorados con motivos vegetales o historias del Nuevo Testamento.

El transepto está cubierto con bóveda de cañón, mientras que las naves originariamente tenían cubierta de madera mudéjar. En 1669 se sustituyeron por las actuales cubiertas barrocas.

El ábside central es de mayores dimensiones que todos los otras. Está decorado internamente con una galería de diez arcos ciegos apoyados en parejas de columnas con los capiteles bellamente esculpidos. Sobre una línea de imposta ajedrezada encontramos tres grandes ventanas de medio punto decoradas con una arquivolta apoyada en columnas y con un guardapolvo que las protege. Por encima de estas ventanas encontramos otra imposta que marca el inicio de la bóveda de cuarto de esfera.

En los pilares que separan los ábsides podemos ver cuatro imágenes correspondientes a pinturas del siglo XIII que representan a cuatro santos.

Los ábsides laterales son mucho más austeros y sólo tienen una ventana de medio punto con un guardapolvo ajedrezado. En el inicio de la bóveda también podemos ver una imposta con ajedrezado jaqués.

Exteriormente todos cuatro ábsides están divididos verticalmente por columnas acabadas en capiteles esculpidos. El central y el más moderno también lo están horizontalmente gracias a una línea de imposta. En los cuatro encontramos una moldura esculpida con motivos vegetales bajo el tejado. Esta se apoya en canecillos esculpidos.

El resto de muros del templo también tienen interesantes canecillos esculpidos.

A finales del siglo XII y en el XIII se añadieron al templo dos galerías porticadas, paralelas a las naves laterales. La del lado sur protege una bella portalada, formada por cinco arquivoltas esculpidas con motivos florales y boceles . Estas se apoyan en columnas con capiteles esculpidos con animales enfrentados. Las arquivoltas rodean uno de los pocos tímpanos esculpidos de la provincia de Segovia. Su erosión no nos permite identificar las cuatro imágenes que hay esculpidas.

La portalada del muro norte mantiene características similares, pero sin tímpano.

En el muro oeste se abre otra puerta enmarcada entre dos grandes contrafuertes, que sirven para delimitar el espacio que ocupa cada nave. La puerta tiene tres arquivoltas de medio punto esculpidas con motivos florales y ajedrezados. Los capiteles en que descansan están decoradas con figuras humanas y bestias imaginarias. Corona la fachada un ventanal de medio punto decorado con una arquivolta con columnas y capiteles esculpidos. Entre la ventana y la puerta posteriormente se abrieron tres ventanas de medio punto.

El pórtico del lado sur es el más antiguo de los dos que tiene el templo. Está formado por un total de once arcos de medio punto, contando el de acceso. Están agrupados en grupos de tres y se apoyan en columnas dobles. Las de los extremos de cada grupo de tres están adosadas a un pilar. La talla de sus capiteles es de mayor calidad que la de los del pórtico norte. En ellos se pueden ver animales, temas vegetales y también escenas referentes a la Natividad de Cristo.

En el pórtico norte  la talla de los capiteles y de los arcos es más tosca, predominando los motivos vegetales.

El campanario está adosado al muro norte. Tiene planta cuadrada y en su base se adosó un ábside en pleno siglo XIII. Pertenece al templo edificado en el siglo XI, si bien hay quien apunta que podría ser del siglo X. Posteriormente se decoró con esgrafiados típicos segovianos y con una nueva cubierta.