És un edifici d’estil gótic i renaixentista que ha tingut diverses etapes constructives al llarg del temps.
Les restes del primer edifici es troben en el pati del Palau, baix del paviment actual, i també en el espai entre les torres corresponents al costat oest. Son fragments de murs construïts amb tapial, la seua disposició no té ninguna relació amb la planta actual de l’edifici, i per les seues característiques i per la ceràmica trobada deuen de correspondre a l’època musulmana, de principis del s.XII, quan Cocentaina seria un poble important, cap de districte, i per tant, aquesta construcció militar podia ser la residencia del governador de la zona.
Com a conseqüència de la repoblació de cristians posterior, realitzada per Jaume I, i de la precària situació d’aquests, front a la nombrosa població musulmana, es va construir una vila de nova planta que es va cercar amb muralles i en l’angle SO es va començar a construir a finals del s.XIII un alcàsser com a residencia del senyor feudal de la població. En aquest moment, les característiques de l’edifici serien les següents:
– Planta quadrangular de 55m de costat amb quatre torres amb els costats reforçats per sillars i coberta almenada.
– Dependencies en les ales Nord i Est, deixant els costats Sud i Oest com a simple mur defensiu, formant part del circuit emmurallat.
D’aquest model hui en dia es manté la planta, les finestres gòtiques que donen al pati i les portes d’arc de mig punt que existeixen en les torres, a més de la principal de la capella i altres que hi ha al pati. Les torres també son d’aquesta època, però eren més menudes, creixeran amb la reforma dels Corella que també modificaran l’interior. Aquest alcàsser cristià va tindre diversos senyors com l’almirall d’Aragó, Roger de Llúria, altres nobles il·lustres, a més de varies reines d’Aragó. Va patir destrosses en la guerra de l’Unió (1348) i quan Cocentaina va ser cremada pels moros de Granada a principis del s.XIV. També va servir ocasionalment com a residencia de les autoritats municipals. Va ser per tant, símbol del poder feudal.
Una vegada la vila va passar a mans dels Corella en 1448, l’alcàsser de caràcter més bé militar, es va passar a convertir en una residencia senyorial, el que justifica que a partir d’aquest moment s’anomenarà Palau. Els comtes van començar una sèrie d’obres que li donaran l’aspecte que te en l’actualitat, la reforma va consistir fonamentalment en una elevació de l’edifici, es van elevar les dues torres existents destinant els espais resultants a l’almacenatge dels productes amb que es pagava als comtes i també com habitació de servici, es va construir a més l’ala sud i es va posar al mateix nivell tot el pis principal on es trobaven les principals estances, per això es van tindre que modificar els nivells de les torres, quedant tapiats alguns espais d’època anterior. Aquesta etapa es caracteritza per l’ús de la rajola i l’argamassa com a material, en lloc del tapial anterior.
L’ultima obra realitzada pels Corella va ser la del pati, de la que hui en dia només queda la fatxada orientada cap al Nord. Te dos pisos, la planta baixa te cinc arcs i el pis superior cinc finestres.
Possiblement aquesta obra es va dur a terme a principis del segle XVII i va quedar interrompuda, donant-se a terme només en un dels quatre costats del pati, la causa, tal vegada, va ser l’expulsió dels moriscos que va privar als Corella de bona part dels seus ingressos. A més durant el segle XVI els comtes de Cocentaina van estar de forma freqüent absents del comtat, encara que quedaria la seua família però aquesta presencia seria cada vegada més esporàdica.