Olmedo debe o seu nome á abundancia deolmos que existían no seu termo.
Foi unha das poboacións conquistadas porAfonso VI antes de1085 e repoboada en1093 outorgándoselle o foro deRoa.
En1353 estivo na localidadePedro I o Cruel, fuxindo da súa esposa para volver reunirse conMaría de Padilla, cuxa filla adulterina, Constanza, Duquesa de Lancaster, recibiu Olmedo e outras vilas a cambio da renuncia aos seus dereitos á coroa que outorgou en1388.
Pasou máis tarde ao dominio deAragón, cando este declarou a guerra aXoán II de Castela, Olmedo aliouse con Xoán II, sendo severamente castigada. O rei deCastela presentouse co seu exército a cercala, e venceu aos aragoneses naPrimeira Batalla de Olmedo. Os aragoneses abandonaron Olmedo esa mesma noite.
En1467 foi corte do infante Don Afonso, levantado en armas contraHenrique IV, e o20 de agosto se trabó xunto a Olmedo unhabatalla en que este quedou vencedor; pero non chegou a entrar na cidade, a cal, ao ano seguinte, pasou a poder da princesa que había de serIsabel a Católica. O seu esposoFernando, despachou aquí a súa convocatoria dasCortes de Aragón que en1515 reuniríanse enCalatayud.
A importancia que se daba a Olmedo naquela época dedúcese do refrán:
"Quen señor de Castela queira ser a Olmedo do seu parte ha de ter".
Filipe V, o primeiro Borbón rei deEspaña, concede un privilexio a Olmedo, que é asinado despois polos seus sucesores. En1811, o francésJosé Bonaparte, entón monarca por dereito de conquista, pasou uns días aloxado na vila.
Celebran na vila dúas festas ao ano, unha relixiosa no Aniversario da Coroación da Virxe da Soterraña, o10 de outubro, e outra máis laica e popular ao redor das festas de San Miguel e San Jerónimo, o 29 e 30 de setembro. Dentro destas festas, destacan os seus encerros tradicionais, declarados Festa de Interese Turístico Rexional.