Va ser construir pels àrabs en data desconeguda, encara que no després del segle xiii, ja que les fonts àrabs ja l'esmenten el 1172. S'ha especulat molt sobre la possibilitat que la fortalesa s'aixeque sobre una fortificació o vil·la romana anterior, encara que l'arqueologia no ha posat llum sobre este assumpte.

Fou una important plaça fort dels musulmans, i mostra de la seua robustesa és que les tropes de Jaume I hagueren d'assetjar-lo tres vegades per aconseguir de prendre'l, finalment, el 1240, amb un exèrcit aragonès format pels cavallers de l'orde de Calatrava, amb mercenaris almogàvers, comanats per Ruy Pérez Ponce de León, comenador d'Alcanyís. Aquestes incursions suposaven una violació del Tractat de Cazola, segons el qual, Villena pertanyia a l'àmbit de conquesta castellana. Passaria definitivament a mans castellanes en virtut del Tractat d'Almizra. Primer es donà en tinença als cavallers de Calatrava, però prompte passà al poder de l'infant Joan Manuel de Borgonya i de Suàbia en ser nomenat senyor de Villena. Després, va passar a mans del seu fill, l'insigne escriptor Joan Manuel de Castella, qui es casà amb la infanta Constança d'Aragó i d'Anjou, filla de Jaume el Just a l'edat de 6 anys, i la tingué reclosa al castell fins que arribà als dotze anys i pogué consumar el matrimoni. L'estada de Constança obligà a Joan Manuel a efectuar reformes per millorar la seguretat de la plaça. Mentre residia a Villena, les seues principals ocupacions foren la literatura i la caça,[1] molt abundant en aquella època segons ell mateix relata:

Després de la casa dels Manueles, fou Alfons IV de Ribagorça el posseïdor de la fortalesa, en ser nomenat primer marqués de Villena. Si hi havia restes del pas del primer marqués pel castell, Joan Pacheco, segon marqués de Villena, s'encarregà de fer-los desaparéixer. A ell es deuen els revestiments dels murs, el segon llenç de muralles i els cossos trecer i quart de la torre, que convertiren la fortalesa en un castell-palau. El 1476, encoratjat pels Reis Catòlics, el poble de Villena s'alçà contra el marqués Diego López Pacheco en un aldarull que valgué la vida de milers de jueus i conversos que van refugiarse al castell. Des d'aleshores, ni la ciutat ni el castell eixiren dels dominis reials, i el marquesat quedà convertir en títol honorífic.

La fortalesa tingué un important paper a les Germanies, ja que s'hi va refugiar el virrey Diego Mendoza en haver sigut derrotat a Gandia, i d'ací partiren les tropes per arrabassar el poder dels sublevats a la ciutat de València. També fou escenari important a la Guerra de Successió Espanyola, quan 50 homes fidels als borbons suportaren un setge de 8 dies dels austriacs, als qui, finalment, feren alçar el setge. Este fet li valgué el títol de Fidelísima, que afegí als que ja posseïa de Muy Noble y Muy Leal.[1]

Fins i tot ja a la Guerra del Francés fou el castell de la Talaia punt estratègic, fet pel qual ordenà el mariscal Louis Gabriel Suchet volar les cobertes de la torre mestra, incloent gran part de les dues voltes almohades, que, amb les del castell de Biar, són unes de les més antigues d'Espanya i de tot el Magreb.