Fue punto estratégico en la época de los celtíberos y los romanos, además de una marca del camino que unía Aragón y Navarra. Su topónimo se remonta a Malia o Manlia, ciudad celtíbera citada en la guerra numantina. Muy cerca se encontraba la mansión Balsio o Balsione, dentro de la calzada romana que unía Tarraco con Asturica.
El templo fue levantado en tres etapas: románica (XII), gótica (XIII) y tardo-barroca (XVIII). Contaba con una capilla de Santiago hasta el siglo XVI. Perteneció a la Orden de los Hospitalarios de San Juan (XII-XIX).