Habitée dans les temps anciens par les Cariens, Kalymnos était sous l'influence de Kos, et du fait de sa distance d'Athènes largement autonome. Kalymnos est citée dans Iliade d'Homère dans le Catalogue des vaisseaux du deuxième chant (676-680) comme apportant avec Cos, Nissiros, Kassos, et Karpathos, trente vaisseaux sous le commandement de Phidippe et Antiphos à l'armée des Argiens menée par Agamemnon et Achille. Avec l'avènement de l'Empire macédonien sous la direction d'Alexandre le Grand, les îles du Dodécanèse s'intègre à l'Empire. À la mort de ce dernier, Kalymnos passe sous le contrôle de Ptolémée Ier. La grotte des Nymphes était un lieu de culte dans l'Antiquité. L'île est l'une des premières au début II siècle à se convertir au christianisme en raison de la proximité de Patmos où Jean l'Évangéliste séjourna.
Au Moyen Âge, elle devint byzantine et fut, durant le XIII siècle, utilisée comme base navale par les Vénitiens. En 1310, elle devint possession des chevaliers de l'Ordre de Saint-Jean de Jérusalem, qui construisirent un important château, puis fut souvent attaquée par les Ottomans (notamment en 1457 et 1460) avant d'être conquise par eux en 1522. Contrairement à ce qui s'est passé à Rhodes et Kos, il n'y eut pas de colonisation turque de l'île qui resta essentiellement de population grecque mais sous domination ottomane pendant quatre siècles, jusqu'au début du XX siècle.
Le 12 mai 1912, lors de la guerre italo-turque, Kalymnos fut occupée par les marins de la Regia Marina. L'Italie prit le contrôle de l'île et du Dodécanèse jusqu'en 1943. Cette période de colonisation italienne fut marquée à Kalymnos, et d'une certaine manière dans tout le Dodécanèse, par le tracé des routes qui demeurent de nos jours ainsi que par l'appropriation de certaines coutumes culinaires. La chute de l'Italie mussolinienne en 1943 poussa les Allemands à entreprendre la campagne du Dodécanèse en octobre 1943, où victorieux après la bataille de Cos, ils occupent tout le Dodécanèse jusqu'à l'armistice de mai 1945. À cette date, Kalymnos passe durant deux ans sous protectorat britannique puis retourne en 1947 à sa patrie grecque pour la première fois en cinq siècles.
On peut noter qu'un sérieux incident, en 1996, faillit provoquer une confrontation militaire entre la Grèce et la Turquie à propos d'un minuscule îlot rocheux et désert, nommé Imia, légalement rattaché à Kalymnos mais dont les Turcs, qui le revendiquaient, tentèrent de prendre possession militairement. Le désaccord fut réglé l'année suivante en respect de la Convention de Montego Bay, établissant la souveraineté grecque. Le vieux ressentiment anti-turc kalymniote reste malgré tout fort, malgré le rapprochement des deux pays depuis 2000, à la suite du tremblement de terre dévastateur en Turquie du 19 août 1999 qui fit 17 000 morts.
Kalymnos est une île qui fut longtemps relativement pauvre, ce qui entraîna une forte émigration de sa population au cours du XX siècle. On retrouve ainsi des familles issues de descendants kalymniotes aux États-Unis et en Australie, notamment à Tarpon Springs en Floride et Darwin dans le Territoire du Nord de l'Australie.
