Möglicherweise beschäftigten sich vom 9. bis 11. Jahrhundert, zu Zeiten von Al-Ándalus, die Bewohner einiger Festungen im Caroig-Massiv und im Hochplateau Muela de Cortes mit dem Fällen von Kiefern und transportierten das Holz vom bergigen Landesinneren zum Hafen von Cullera. Von dort exportierte man das Holz zu anderen Orten von Al-Ándalus, in die Maghreb-Region oder ins baumlose Nildelta. Jedoch entwickelte sich erst ab dem 12. Jahrhundert in der Zone ein ausgefeiltes, mit einem Kataster arbeitendes System der gemeinschaftlichen Zuflucht und militärischen Verteidigung. Als das Ebro-Tal, Cuenca und Teruel in die Hände von Kastiliern und Aragoniern übergingen, entstanden Kompanien von Rittern und almogávares genannten aragonesischen Infanterie-Soldaten, die über die Grenze am Júcar-Fluss hinweg muselmanische Weiler (alquerías) plünderten. Auf diese Zeit geht die auf nacktem Fels 310 Meter hoch gelegene andalusische Festung zurück, die man heute unter der Verkleinerungsform el Castillet kennt. Es handelte sich um ein Bauwerk aus Lehmmauern (tâbiya, Verschalung) auf einem Sockel aus Bruchstein-Mauerwerk.
Unter dem almohadischen Kalifat, das in den Jahren 1172 bis 1240 die Iberische Halbinsel beherrschte, sprießten Burgen unterschiedlicher Art aus dem Boden. Meist verfügten sie über Türme mit einem albacar, einem angegliederten Bereich. Die Architekten Javier Hidalgo und Ignacio Matoses haben bis zu 15 Festungen aus andalusischer Zeit an beiden Ufern des Júcar ausgemacht, von Cofrentes bis Tous. Vier dieser Burgen liegen in Millares: Es handelt sich um Cavas, el Castillet, el Corraliquio l’Antón und das fast verschwundene Castillo del Medio (mittlere Burg) im Ort (davon sind einige Lehmmauern in der Castillet-Straße erhalten). Die letztgenannte Burg mit Turm, Einfriedung und Vogt-Wohnhaus war möglicherweise das Haus des Dorfherren. Im 13. Jahrhundert errichteten die ersten Feudalherren diese Festung, die das Castillet ersetzte. Später (im 16. Jahrhundert) begünstigte und beschleunigte der Bau des Palastes der Bou am Platz das Verlassen und den Verfall dieser Burg. Dennoch war es das sogenannte Castillet, auch Castillo de Abajo (untere Burg) auf dem Felsen gegenüber – nicht die Burg im Ort selbst –, die jahrhundertelang den Namen Castillo de Millares trug, wie mittelalterliche Dokumente belegen.
Um das Gebäude islamischen Ursprungs herum ist die Befestigungsmauer erhalten, obgleich sie Einstürze erlitten hat und insgesamt recht abgetragen ist. Nur der zur Mittagssonne hin ausgerichtete Hauptturm rechteckigen Grundrisses ragt deutlich über den Rest der Ruine heraus. Die Konturen der umlaufenden Mauer sind recht unregelmäßig. Neben dem erwähnten südlichen Hauptturm zeigt ein kleinerer Turm in nordwestliche Richtung. Er verteidigt den Zugang zum Burggelände an einer strategischen Mauerkrümmung. Ein solcher Eingang mit vorgelagertem Schutzwall ist in der almohadischen Festungsbaukunst häufig zu finden. Im größeren Turm sind Reste der Dachkonstruktionen erhalten: Der glatte Stein ihrer Tonnengewölbe ist mit Kalkmörtel zusammengefügt. Nach den Autoren Hidalgo und Matoses kam diese Bauform auch in der Zugangskuppel der unweit gelegenen Pileta-Burg am nördlichen Ortsrand von Cortes de Pallás zum Einsatz.