Temple construït a partir de l'any 1080 per Raimund de Borgonya. Ubicada en el conegut com Arrabal Major, un barri que durant l'edat mitjana estava ocupat per teixidors i moriscos.  D'aquesta edificació només ens ha arribat la torre. Cap a l'any 1111 Alfons I el Batallador, rei d'Aragó i també de Castella, gràcies al seu matrimoni amb doña Urraca. Aquest matrimoni va ser clau en la definició de la planta del nou temple, ja que Alfons I va voler que fos una rèplica de la catedral de Jaca. És per això que San Millán sorprèn per ser una "església aragonesa" en mig de Castella.

Té planta basilical formada per tres naus dividides en cinc trams. També té transsepte, que sobresurt en alçada, però no en planta,  en el que originàriament s'obrien tres absis. Posteriorment encara s'hi afegí un absis més pel costat nord.

En la intersecció entre la nau principal i el transsepte s'alça una cúpula sobre trompes. En aquest cas està reforçada per dos parells d'arcs que en creuar-se formen un quadrat.

Les naus, com en Jaca, estan separades per arcs formers de mig punt que es recolzen de forma alternada en columnes adossades al pilars cruciformes i en grans columnes cilíndriques. Tant unes com les altres tenen grans capitells decorats amb motius vegetals o històries del Nou Testament.

El transsepte està cobert amb volta de canó, mentre que les naus originàriament tenien coberta de fusta mudèjar. En 1669 es van substituir per les actuals cobertes barroques.

L'absis central es de majors dimensions que tots els altres. Està decorat internament amb una galeria de deu arcs cecs recolzats en parelles de columnes amb els capitells bellament esculpits. Sobre una línia d'imposta escacada trobem tres grans finestres de mig punt decorades amb una arquivolta recolzada en columnes i amb un guardapols que les protegeix. Per sobre d'aquestes finestres trobem una altra imposta que marca l'arrancada de la volta de quart d'esfera.

En els pilars que separen els absis podem veure quatre imatges corresponents a pintures del segle XIII que representen a quatre sants.

Els absis laterals són molt més austers i només tenen una finestra de mig punt amb un guardapols escacat. En l'arrancada de la volta també podem veure una imposta amb escacat jaqués.

Exteriorment tots quatre absis estan dividits verticalment per columnes acabades en capitells esculpits. El central i el més modern també ho estan horitzontalment gràcies a una línia d'imposta. En tots quatre trobem una motllura esculpida amb motius vegetals sota la teulada. Aquesta es recolza en mènsules esculpides.

La resta de murs del temple també tenen interessants mènsules esculpides.

A finals del segle XII i en el XIII es van afegir al temple dues galeries porticades, paral·leles a les naus laterals. La del costat sud protegeix una bonica portalada, formada per cinc arquivoltes esculpides amb motius florals i bossells. Aquestes es recolzen en columnes amb capitells esculpits amb animals enfrontats. Les arquivoltes envolten un dels pocs timpans esculpits de la província de Segòvia. La seva erosió no ens permet identificar les quatre imatges que hi ha esculpides.

La portalada del mur nord manté característiques similars, però sense timpà.

En el mur oest s'obre una altra porta emmarcada entre dos grans contraforts, que serveixen per delimitar l'espai que ocupa cada nau. La porta té tres arquivoltes de mig punt esculpides amb motius florals i escacats. Els capitells on descansen estan decorades amb figures humanes i bèsties imaginàries. Corona la façana un finestral de mig punt decorat amb una arquivolta amb columnes i capitells esculpits. Entre la finestra i la porta posteriorment es van obrir tres finestres de mig punt.

El pòrtic del costat sud és la més antiga de les dues. Té un total d'onze arcs de mig punt, comptant el d'accés. Estan agrupats en grups de tres i es recolzen en columnes dobles. Les dels extrems de cada grup de tres estan adossades a un pilar. La talla dels seus capitells és de major qualitat que la dels del pòrtic nord. En ells es poden veure animals, temes vegetals i també escenes referents a la Nativitat de Crist.

En el pòrtic nord  la talla dels capitells i dels arcs és més tosca, predominant els motius vegetals.

El campanar està adossat al mur nord. Té planta quadrada i en la seva base es va adossar un absis en ple segle XIII. Pertany al temple edificat al segle XI, tot i que hi ha qui apunta que podria ser del segle X. Posteriorment es va decorar amb esgrafiats típics segovians i amb una nova coberta.