En principio el topónimo, de gran importancia cultural, es una muestra clara más de la palabra árabe madīna, pronunciada en árabe de España medina (y como tal incluso adaptada a menudo en lengua castellana) y un segundo elemento que ha sido objeto de debate y discusión. Básicamente las opciones son dos, pero esas dos opciones, como se intentará hacer ver, no son absolutamente opuestas entre sí. 

La primera de ellas es ver en el segundo elemento la continuación del topónimo romano preexistente a la ocupación árabe de la zona, pues la localidad tuvo un importante pasado romano indiscutible. A pesar de las dificultades parece que puede ser identificada con la ciudad de Ὄκιλις, que tenemos documentada solo en esta forma griega por Apiano. En Medinaceli se han hallado ampliamente materiales celtibéricos, y muchos materiales constructivos, mosaicos, etc. de la época hispanorromana, lo que aegura fuera de toda duda razonable el poblamiento prerromano y romano. Este topónimo, por supuesto, no es latino, sino celta. Como en otros casos, se ha adaptado a la lengua latina, y su propia flexión nominal suponemos, un topónimo preexistente. El árabe simplemente habría antepuesto la palabra  medina al topónimo preárabe que habría evolucionado fonéticamente según las reglas del latín tardío. Esta interpretación contaría a su favor con el hecho de que la ciudad romana con seguridad existió y tuvo gran importancia, como prueba su famoso arco.  Hay otros muchos casos absolutamente paralelos, como Medina Sidonia en el que el término árabe, simplemente, se antepone al romano que a su vez es adaptación del prerromano existente en la época de la llegada de la lengua latina a la zona. El principal problema de esta hipótesis, en todo lo demás intachable, es que causa estupor el hecho de que no haya un solo documento epigráfico con el nombre de la ciudad, ninguna alusión a su existencia en los textos literarios, fuera del citado de Apiano. 

Una segunda posibilidad, principalmente estimada por arabistas, es suponer que el segundo elemento no es el resultado del latín *Ocilim o similar, sino simplementre un conocido antropónimo árabe Sálim, de donde  Madínat Sálim (ár. clás. Madīnat Sālim) 'la ciudad de Sālim' > Medinaceli. Es interpretación contaría a su favor con las grafías con consonante final /m/ que hallamos en la documentación antigua. Los inconvenientes a los que se enfrenta son grandes, por lo demás, principalmente la propia adaptación del antropónimo árabe en castellano, el que el nombre de la ciudad romana (porque, evidentemente, tuvo que tener un nombre) hubiera sido totalmente olvidado, etc.