Los restos más antiguos se localizan a un kilómetro escaso del casco urbano actual, junto al río Huecha, en el cerro de "El Convento". Datan de la Edad del Hierro. Allí se emplazaba el enclave celtíbero conocido por los textos antiguos como la Belsinon y posteriormente como la Balsio o Balsiones romana. Éstos establecieron allí una parada o "mansión" en la vía nº 32 de Tarraco a Astúrica. En el yacimiento arqueológico se han encontrado numerosos objetos de cerámicas de diversas procedencias. Este yacimiento, declarado Bien de Interés Cultural en 1992, destaca por la gran cantidad de cerámica rojiza de terra sigillata encontrada durante las excavaciones; el lugar fue abandonado en el siglo III d.C. Un nuevo asentamiento se fraguó poco después en torno a una villae rusticae, hoy casco urbano de Mallén, cuyo nombre deriva de un antropónimo romano.
En 1119 Alfonso I reconquistó la villa a los árabes, y la repobló con mozárabes después de una incursión en tierras andaluzas (1126). En 1132 por medio de una Carta Magna le concedió fueros. Y ese mismo año dona la villa de Mallén, de forma conjunta, a las Órdenes del Temple y de San Juan de Jerusalén. Sin embargo fueron los hospitalarios quienes se instalaron en el castillo de Mallén, regidos desde 1144 por Guillem de Belmes, Prior de Aragón y Catuluña. En 1151 Ramón Berenguer IV confirmó la posesión de Mallén para los sanjuanistas, y la de Novillas para los templarios. Años después crearon una encomienda que incluía las poblaciones de Fuendejalón y Gallur. Los sanjuanistas conservaron su jurisdicción hasta los inicios del siglo XIX.
En 1209 en la villa se produjo el encuentro entre Pedro II de Aragón y Sancho VIII de Navarra para resolver sus desavenencias. Gracias a una sentencia arbitral, en 1354, el concejo fue autorizado para elegir a sus miembros, salvo al justicia, que lo seguiría eligiendo el comendador, al que se debía rendir homenaje. En 1452 se utilizó su castillo como prisión para don Carlos, príncipe de Viana, por mandato de su padre Juan II.
La Guerra de Sucesión fue funesta para Mallén. En 1706 fue sitiada y saqueada por tropas del archiduque Carlos, pretendiente al trono de España. La valerosa lucha de los habitantes de la villa le valió los títulos de “Leal y siempre fidelísima”, otorgados por el rey Felipe V.
Entre 1808 y 1813, durante la Guerra de la Independencia, su castillo cobijó a una guarnición francesa, además de convertirse en un centro de recaudación de suministros para los invasores. En el verano de 1813 la fortaleza sufrió muchos daños en las luchas que llevaron a la liberación de la ciudad por las tropas españolas al mando del Francisco Espoz y Mina, y una vez derrotado el ejército francés el castillo fue desmantelado; y sus piedras aprovechadas para reconstruir los edificios de la villa.