A vila pertenceu á Coroa de Castela ata que en 1439 foi cedida a Íñigo López de Mendoza, marqués de Santillana, quen en 1451 a permutou pola vila de Saldaña con Alonso de Fonseca e Ulloa, bispo de Ávila e arcebispo de Sevilla. En 1453, Alonso de Fonseca e Ulloa obtivo do rei Xoán II de Castela o permiso real para edificar o castelo, aínda que a súa construción non se empezou ata varios anos despois. Pois como tivo que ausentarse de Coca, Alonso de Fonseca e Ulloa cedeu en 1460 os dereitos da vila ao seu irmán Fernando de Fonseca, que os exerceu ata a súa morte en 1463. Alonso faleceu en 1473 sendo arcebispo de Sevilla, e Coca foi herdada polo seu sobriño, Alonso de Fonseca e Abeledo, fillo de Fernando, quen levou a cabo a construción da meirande parte do castelo, ata quedar practicamente rematada en 1493. A partir de entón foi residencia palaciana e escenario de grandes festas, ás cales asistiron notables personalidades.

Nomeou o seu sobriño Alonso de Fonseca e Acevedo coma o seu sucesor, quen mandou construír o castelo en 1473 e converteuno en residencia señorial, onde celebrou grandes festas que eran frecuentadas por diferentes personalidades, entre as que destaca o Cardeal francés Jean Jouffroi, que chegou a Castela coa proposta de matrimonio entre a infanta Isabel (despois raíña) co duque de Berry de Guyena, irmán de Luís XI de Francia. Tamén visitou o castelo Beatriz de Bobadilla, marquesa de Moya.

En 1502, os Reis Católicos aseguráronse de que en caso de morte de Alonso, o castelo pasase ao seu irmán Antonio Fonseca. E no ano seguinte a raíña Isabel decretou que os herdeiros da vila de Coca só poderían ser varóns, dese xeito eliminou a posibilidade de que o castelo fose herdado por unha das dúas únicas fillas do seu dono. Por iso en 1505, Coca paso ao seu irmán Antonio Fonseca, capitán dos Reis Católicos.

En 1504 pasou a ser propiedade de Antonio de Fonseca, que ampliou os elementos defensivos do castelo, que máis tarde tivo que defenderse do infortunado ataque do marqués do Cenete, quen pretendía rescatar a súa prometida, María de Fonseca, que estaba retida polo seu tío. En 1512 traballaron no castelo alarifes sevillanos (mestres de obras), que posiblemente foron os artífices de moitas das súas decoracións. En 1521 foi atacado polas tropas comuneras en represalia polo incendio de Medina del Campo levado a cabo polo propio Antonio de Fonseca; debido a que non puideron conseguir acceder ao castelo, destruíron a fortaleza próxima de Alaejos. En 1645, foi prisión do duque de Medina-Sidonia, Gaspar Pérez de Guzmán, acusado de terse proclamado rei de Andalucía. E máis adiante, por casamentos, o castelo pasou a ser propiedade da Casa de Alba.

En diferentes épocas pasou por importantes reformas: galerías do Patio de Armas no século XVI, das Torres da Homenaxe e de Pedro Mata no século XVII; e outras melloras en 1715. Pero a partir de 1730 o seu arquivo foi trasladado a Madrid, e o castelo caeu no abandono e a rapina. En 1808, durante a Guerra da Independencia, os franceses ocuparon a vila de Coca e as súas tropas instaláronse no castelo causando importantes danos nel. Cando os franceses o abandonaron en 1812 só quedaban del ruínas. E en 1828, un administrador da Casa de Alba sen escrúpulos vendeu materiais do castelo, entre eles columnas de mármore do patio, o que acentuou aínda máis a súa ruína.

En 1926, o castelo foi declarado Monumento Nacional. En 1931 foi declarado Ben de Interese Cultural. En 1954 foi cedido ao Ministerio de Agricultura por un período de tempo de 100 anos menos 1 día, sendo restaurado entre 1956 e 1958 para acoller a Escola de Capacitación Forestal. En 1994 foi escenario dun dos capítulos do concurso televisivo de TVE titulado La noche de los castillos.