The site of Karytaina is often identified with the ancient city of Brenthe, but although a settlement certainly existed there before the Frankish conquest in ca. 1205, few archaeological remains survive. The Greek archaeologist N.K. Moutsopoulos has suggested the existence of a 12th-century church inside the Karytaina Castle.
With the Frankish conquest and the establishment of the Principality of Achaea, Karytaina became one of the secular baronies into which the Morea was divided by the Crusaders. Karytaina was one of the largest baronies, and of special strategic importance: its position allowed it to control the southern part of the mountainous Skorta region and, through the ravine of the Alpheios valley, the main route connecting the Arcadian plateau with the coastal plains of Elis. The barony belonged to the Briel or Bruyères family. The third baron, Geoffrey of Briel, built the Castle of Karytaina and played a major role in the affairs of Frankish Greece in the middle of the 13th century, repeatedly defying even the Prince William II of Villehardouin. After Geoffrey's death in 1275, the barony gradually reverted to the princely domain, and was later held by Isabella of Villehardouin and her daughter, Margaret of Savoy. From the late 13th century, Karytaina was increasingly threatened by the attacks of the Byzantine Greeks of Mystras, until it finally fell to them in 1320.
The town and its castle lost their importance thereafter, and are only intermittently mentioned in the 14th–15th centuries until the time of the Ottoman conquest in 1460. The 17th-century Ottoman traveller Evliya Çelebi mentions the town but did not visit it, while under Venetian rule (1687–1715) only the town, and not the castle, is mentioned by the Venetian governors. During the second period of Ottoman rule after 1715, the castle was abandoned and fell in ruins, and remained so until the 19th century. The town itself grew in importance as the centre of a district (kaza) and a marketplace, especially for wheat; it was also a centre for silk and carpet manufacture. At the turn of the 18th century, François Pouqueville recorded that the district comprised 130 villages with 28,170 inhabitants, of which 3,000 in Karytaina itself.
Karytaina was taken by the Greek rebels on the outbreak of the Greek War of Independence in 1821, and formed one of the first strongholds of the rebellion, earning the nickname "Bastion of 1821". In 1826 Theodoros Kolokotronis used it as a base of operations against Ibrahim Pasha of Egypt and as a shelter for women and children.