Coca to dawna rzymska Cauca. Według późnoantycznych kronikarzy, m.in. Hydacjusza, urodził się tu ok. 347 r. cesarz Teodozjusz Wielki, ostatni władca całego Imperium Rzymskiego (część badaczy wskazuje raczej Italikę pod Sewillą). Zamek stoi poza miasteczkiem, na skraju skarpy nad rzeką Voltoyą, niedaleko jej ujścia do Eresmy. W 1451 r. Coca przeszła w drodze zamiany na własność Alonsa de Fonseki, biskupa Ávili i arcybiskupa Sewilli. W 1453 r. król Jan II zgodził się na budowę zamku. Większość prac przypadła jednak na czasy jego bratanka, Alonsa de Fonseki y Avellaneda, pana Coki i Alaejos, a pod koniec stulecia budowla była prawie gotowa. Fonsekowie sprowadzili z Ávili mudéjarskiego mistrza Alí Caro, który z braćmi Yuçafem i Abceytem zaprojektował i budował zamek. Mudéjarzy, czyli muzułmanie żyjący pod władzą chrześcijańskich królów, byli wtedy w Kastylii najlepszymi mistrzami cegły, a Alí Caro prowadził w tym samym czasie także budowy w Ávili.

Coca jest jak pokaz możliwości cegły. Dwa kwadratowe obwody murów otacza głęboka sucha fosa, a narożne wieże są wieloboczne, z pionowymi żebrami i gęstwiną ceglanych wieżyczek i blanek. Z daleka wygląda to raczej jak dekoracja niż twierdza. Kamień wapienny pojawia się tylko w strzelnicach w kształcie krzyża z okrągłym otworem i w kolumnach dziedzińca. Był to w istocie pałac obronny: w XV w. gościli tu m.in. francuski kardynał Jean Jouffroy i Beatriz de Bobadilla, przyjaciółka Izabeli Katolickiej. W wieży głównej zachowała się zbrojownia z gotyckim sklepieniem obłożonym kolorowymi płytkami, a w kilku salach resztki mudéjarskich tynków i malowideł. Z jej szczytu widać podobno zamki w Cuéllar i Íscar. Do dziś uchodzi za najwspanialszy przykład gotycko-mudéjarskiej architektury obronnej w Hiszpanii, a jego makiety stoją w parku mudéjaru w pobliskim Olmedo i w parku miniatur Minimundus w austriackim Klagenfurcie.

W 1504 r. zamek odziedziczył Antonio de Fonseca. To ten sam dowódca królewski, który w sierpniu 1520 r. kazał podpalić Medina del Campo, gdy mieszkańcy nie chcieli wydać dział. Rok później comuneros oblegali Cocę, ale jej nie zdobyli i w odwecie zniszczyli zamek Fonseków w Alaejos. W 1645 r. więziono tu księcia Medina Sidonia, a przez małżeństwa zamek przeszedł do domu książąt Alby. Po 1730 r., gdy archiwum rodu przeniesiono do Madrytu, opustoszał. W czasie wojny z Napoleonem zajęli go Francuzi i do 1812 r. zostawili w ruinie, a w 1828 r. zarządca Albów sprzedał z niego materiały, w tym marmurowe kolumny dziedzińca. W 1954 r. książęta Alby oddali zamek państwu w użytkowanie na sto lat bez jednego dnia. Po odbudowie w latach 1956–1958 otwarto w nim szkołę leśną, w której kształcą się leśnicy [obecna nazwa i działalność do sprawdzenia]. W kościele Santa María la Mayor w miasteczku stoją renesansowe nagrobki Fonseków z marmuru kararyjskiego, wykonane we Włoszech przez Domenica Fancellego i jego hiszpańskiego ucznia Bartolomégo Ordóñeza.