La ermita de la Magdalena ocupa el monte del mateix nom, que s'alça sobre Castelló. L'ermitori té el seu origen en el segle XIII, després de la conquista cristiana de 1233. La primera referència documental a una processó de penitència que va arribar fins a l'ermita del Castell Vell data de 1375, quan la ciutat patia una epidèmia de pesta negra. D'aquella primitiva ermita no s'ha conservat res, ni tan sols el record de la seua ubicació exacta.

La construcció de l'ermita actual va començar en 1451, obra d'un frare del Monestir de Santes Creus conegut popularment com el frare barbut, de nom real Antoni. Va aprofitar una antiga cisterna de grans proporcions excavada en la roca i va aixecar un edifici estructurat en dos naus paral·leles separades per arcs rudimentaris, cobert amb bòveda de canó. El pòrtic d'entrada, amb arc de mig punt de dovelles regulars, es va afegir en 1455, i la capella es va construir en 1456. Entre eixa data i 1590 es van succeir diverses obres de reforma i ampliació: es va dotar l'altar major d'un retaule de fusta i es van reedificar les cavallerisses per al servici dels pelegrins. La forma definitiva que presenta avui el conjunt —ermita-hospederia amb torre adossada que actua de campanari— va ser establida en 1758 per Vicente Pellicer.

Com a meta de rogatives i pelegrinacions durant l'Edat Mitjana i en èpoques posteriors, l'ermitori disposava de cuines, menjador, cisternes i hospederia, que el Consell Municipal —propietari de la casa i ermita de Santa Magdalena— reconstruïa i reformava periòdicament. Junt a l'ermita es troben els restes del castell, del qual es conserven un tram de muralla i dos murs de calicant. Juan Bautista Balbás, en el seu Libro de la Provincia de Castellón de 1892, va documentar el hallatge en els estrats inferiors del Castell Vell de basaments de columnes, monedes i sèpulcres romans; excavacions posteriors van treure a la llum tègules empleades en enterraments i fragments de ceràmica sigil·lata.

El conjunt va ser declarat Bé d'Interés Cultural en 1996.