Σύμφωνα με το μύθο, οι πρώτοι άνθρωποι που κατοίκησαν στο νησί, έκλεψαν τους Θεούς από τον Όλυμπο και τους έφεραν στο νησί τους. Για το λόγο αυτό, ονομάστηκαν Αρπάθεοι, ονομασία που αργότερα μετατράπηκε σε Καρπάθεοι και Καρπάθιοι, οπότε και το νησί πήρε το όνομα Κάρπαθος. Μια άλλη μυθολογική εκδοχή θέλει την Κάρπαθο πατρίδα του τιτάνα Ιαπετού, του αδερφού του Κρόνου, και τόπο κατοικίας της Αθηνάς και του Πρωτέα. Σύμφωνα με άλλη εκδοχή, όλοι οι Τιτάνες ζούσαν στο νησί πριν την Τιτανομαχία, την γνωστή μάχη μεταξύ Τιτάνων και Ολύμπιων Θεών. Στη μάχη αυτή, ο Ποσειδώνας πάλεψε με τον Τιτάνα Εφιάλτη, απέκοψε ένα κομμάτι από την πλευρά της Καρπάθου κι έθαψε κάτω από αυτό τον αντίπαλό του. Το κομμάτι αυτό της γης λέγεται πως είναι η νησίδα Σαρία, βόρεια της Καρπάθου.
Σύμφωνα με σύγχρονους τοπικούς θρύλους, στην παραλία Φύσσες, κοντά στην Όλυμπο, ζει ένα θαλάσσιο τέρας. Προφανώς η σκοτεινή και μόνιμα φουρτουνιασμένη θάλασσα, προκαλούσε φόβο στους κατοίκους που δημιούργησαν το θρύλο αυτό.