Olmedo debe su nombre a la abundancia de olmos que existían en su término.

Fue una de las poblaciones conquistadas por Alfonso VI antes de 1085 y repoblada en 1093 otorgándosele el fuero de Roa.

En 1353 estuvo en ella Pedro "El Cruel", huyendo de su esposa para volver a reunirse con María de Padilla, cuya hija adulterina Constanza, Duquesa de Lancaster, recibió Olmedo y otras villas a cambio de la renuncia a sus derechos a la corona que otorgó en 1388.
Habiendo pasado más tarde al dominio de Aragón, cuando este declaró la guerra a Juan II de Castilla, Olmedo se alió con Juan II, siendo severamente castigada, pero el rey de Castilla se presentó con su ejercito a sitiarla, y venció a los aragoneses que la abandonaron esa misma noche.

En 1467 fue corte del infante Don Alfonso, levantado en armas contra Enr¡que IV. è