Gardiki existed as a settlement before the 13th century. Its name, which derives from a Slavic term for "small fort", demonstrates the naturally fortified nature of the site, even before the construction of the castle. The castle of Gardiki was built sometime after 1284, and was in Byzantine hands by 1297, when the Princess of Achaea, Isabella of Villehardouin, constructed the fortress of Chateneuf to protect the inhabitants of the plains of Messenia and Arcadia from the raids of the Byzantine troops based in the region around Gardiki and Mystras. Indeed, it is likely that the castle was built by the Byzantines, as it is not recorded that it was ever held by the Latins of Achaea.
In 1374, the new bailli (viceroy) of the Principality of Achaea, Francis of San Severino, attacked Gardiki, captured the village and defeated a Byzantine relief force, but was unable to capture the strongly fortified castle and had to withdraw.
In 1422, the Republic of Venice considered taking over the two fortresses, along with much of what remained of the Principality of Achaea and parts of the Byzantine Despotate of the Morea, as part of a defensive alliance to protect the Morea from the Ottoman Empire, but nothing came of the negotiations with the local Latin and Greek leaders. As a result, when the Ottomans under Turahan Bey invaded the Morea in 1423, several towns, including Gardiki, were captured and pillaged.
In 1460, during the Ottoman conquest of the Despotate of the Morea, the population of the town of Leontari sought refuge in the Castle of Gardiki. The castle, commanded by Manuel Bochalis, surrendered on condition of safety, but the Ottomans massacred the entire population of 6,000. Only Bocharis and his family escaped this fate, as they were relatives of the Ottoman grand vizier, Mahmud Pasha Angelović.
The exact site of the medieval castle is unknown. The descriptions in the medieval sources do not match with the village of Gardiki (modern Anavryto) to the east of Leontari, where furthermore no traces of fortifications survive. It is more likely that the medieval site is to be found southwest of Leontari, some 8 kilometres (5.0 mi) north of Kalamata, at the ruins of Kokla or Kokkala (close to Ellinitsa), where already Pietro Antonio Pacifico and Jean Alexandre Buchon had proposed as its likely site.