Au moment de l’invasion musulmane en 713 le bourg fit partie des domaines du duc Wisigoth Teodomiro qui arriva à le conserver indépendant. Les musulmans lui donnèrent le nom de Bintla puis Bilyana; à la fin du VIIIe siècle, l’émir Abderraman I rompit unilatéralement les accords et s’empara de la localité. Sur le haut de la colline, avant 1172 on édifia le dit Château de la Atalaya autour duquel s’installèrent les populations musulmanes.
Le Traité de Cazola (Soria) déterminait que la région devait être castillane, mais les aragonais y mirent le siège par trois fois entre 1238 et 1240 jusqu’à en faire la conquête. Pour éviter une guerre avec la Castille ce fut une des localités qui lui furent rendues par le Traité de Almizra (1244). En 1261 elle fut confié à l’Infant Don Manuel de Castille qui dut faire face trois ans plus tard à la rébellion des mauresques. Une fois ceux-ci expulsés du royaume en 1270, on lui concède la charte de droits de Murcia pour attirer les colons chrétiens. La Seigneurie tombe en héritage à son fils, Don Juan Manuel (auteur du livre «Le Comte Lucanor», qui vécut ici avec son épouse, l’Infante Constance d’Aragon, qui n’avait que six ans lors du mariage, devant attendre qu’elle en ait douze Don Juan Manuel entreprit des travaux pour conditionner la forteresse.
Avec d’autres villages Alicantins de la couronne de Castille, en 1304, Villena fut remise au Royaume d’Aragon, mais en 1375 par le Traité de Almazan elle revint à la Castille. Après la Guerre des Pedros entre La Castille et l’Aragon, le roi Enrique II de Castille fit don de cette Seigneurie à l’un de ses principaux partisans, l’Infant Alfonso d’Aragon. Divers petits bourgs des provinces de Albacete, Murcia, Valence, Cuenca, Alicante, Malaga et Badajoz y furent alors incorporés.
De retour au patrimoine de la couronne en 1445, le roi Juan II créa le marquisat de Villena et le donna à son favori, Juan Pacheco dont les intrigues rendirent célèbre le nom de la localité. En 1476, le marquis fit front à Isabelle la Catholique et les habitants prirent le parti de la reine, expulsant les soldats du marquis. Ce devint alors une dépendance directe de la couronne. Son fils don Diego conservera le titre, mais dès lors, Villena ne serait plus qu’une ville royale. Ce qui sera confirmé en 1525 car au moment du soulèvement des Germanias, la ville resta fidèle au roi Carlos I, ce qui lui vaudra le titre de «Très Noble, Fidèle et Loyale» Au moment de la Guerre de Succession, elle conservera cette fidélité et Felipe V lui donnera alors le titre de «Particulièrement fidèle». Ainsi que le droit de célébrer une Foire annuelle en septembre et un marché hebdomadaire chaque jeudi.

Lavandières à Villena, vers 1900
Au XVIIIe siècle ouvrirent à Villena d’importantes fabriques de savons et de lin ainsi que des distilleries de brandy. À la fin du siècle, c’était une ville ouverte, sans murailles.
En 1803, la lagune du village fut asséchée et transformée en terres cultivables. Huit ans plus tard, au cours de la Guerre d’Indépendance, les troupes françaises de Suchet détruisirent le château. En 1858, on construisit le chemin de fer qui unissait Alicante et Alcoy avec Madrid. Finalement, en 1836, Villena fut incorporée à la province de Alicante, et en 1851 y naquit le compositeur de Zarzuelas Ruperto Chapi, en honneur de qui ont lieu des célèbrations chaque année.