UNA VIEJA LEYENDA asegura que, en el emplazamiento que hoy ocupa la iglesia, había un castillo, del cual partía un túnel que llegaba hasta la fortaleza de San Silvestre, también desaparecida. Lo cierto es que la iglesia de Santa María del Castillo, también conocida como Santa María la Mayor, está unida a los restos de uno de los dos cinturones amurallados que tuvo la villa de Olmedo y que fueron construidos durante los siglos XII y XIII. Además, la torre del templo se levanta sobre la base de uno de los antiguos lienzos de mortero de la muralla. El edificio actual muestra una gran cabecera rectangular –con algunos añadidos a mediodía– y larga nave, a cuyo flanco norte se han adosado varias capillas, envuelto todo por el sur y oeste por un airoso pórtico. Sin embargo del primitivo templo románico sólo resta la portada meridional, hoy cegada y en pésimo estado de conservación. Es de piedra, enmarcada en un alfiz de piedra, dispuesta a ras de muro, y formada por arco de ingreso liso y cinco arquivoltas de medio punto, la primera con bocel entre filetes angulosos, la segunda y quinta con ajedrezado, la tercera con pequeños roleos y la cuarta con lo que parecen una serie de toscas hojas planas. Debió tener cuatro columnas acodilladas pero se conserva tan sólo una, a la derecha, cuyo capitel se decora con motivo vegetales a base de pequeñas hojas. A juzgar por la estructura constructiva y por la decoración, muy similares a la de Santa María de la Vega, dicha portada debió levantarse a mediados del siglo XII. A los pies de la iglesia hay una portada, con arco de ingreso y dos arquivoltas más chambrana, con sencillas molduras y apoyos sobre pilastras, con impostas achaflanadas. Es ya un modelo protogótico que podemos fechar dentro del siglo XIII. Durante los últimos años del siglo XV comenzó a levantarse un nuevo templo en estilo gótico tardío que vino a sustituir al anterior. La galería porticada fue construida en 1607 por Francisco Rodríguez, maestro cantero y vecino de Cardeñosa. Por lo que respecta a la torre, obra ya también muy tardía, se aprecia cómo para levantarla se aprovechó un lienzo de la muralla del siglo XIII, que continúa hacia el norte, más allá de la iglesia. Se trata de un muro de mortero terminado en un corto friso de esquinillas de ladrillo, de tipo mudéjar.