Σύμφωνα τους Λατίνους συγγραφείς Τίτο Λίβιο και τον «Ψευδο-Σκύλακα», το Καστελλόριζο εποικίστηκε από τους Δωριείς. Αργότερα κατακτήθηκε από τα Περσικά πλοία και, σύμφωνα με τις υποθέσεις των ιστορικών, κατά τον 4ο αιώνα π.Χ. ήταν μέρος της επικράτειας του ισχυρού κράτους της Ρόδου, και ειδικότερα του δήμου της Περαίας. Από τους χρόνους εκείνους, ή τις αρχές της ελληνιστικής εποχής, βρίσκεται στα ανατολικά του λιμανιού ο περίφημος Λυκιακός Τάφος. Πρόκειται για έναν λαξευτό στον βράχο ταφικό μνημείο με πρόσοψη που διαθέτει αέτωμα το οποίο στηρίζεται σε παραστάδες με ιωνικές βάσεις και επίκρανα. Οι αρχαιολόγοι βρίσκουν συγγένεια των τυπολογικών του στοιχείων με εκείνα της περιοχής της Λυκίας.
Από την εποχή της Ρωμαιοκρατίας έχει διασωθεί αναθηματική επιγραφή που μνημονεύει το όνομα του Σωσικλή Νικαγόρα, που ήταν στρατιωτικός διοικητής από την Ρόδο, και «επιστάτης» στον Ερμή Προπύλαιο (2ος αιώνας π.Χ.). Από την ελληνιστική εποχή χρονολογείται και η εντυπωσιακή οχύρωση του Παλαιόκαστρου που βρίσκεται σε κοντινή απόσταση δυτικά της πόλης του Καστελλόριζου. Το Παλαιόκαστρο μακριά από τη θάλασσα προσέφερε καταφύγιο στους νησιώτες κατά τους δύσκολους εξαιτίας της πειρατείας μεσοβυζαντινούς χρόνους. Επίσης στην βραχώδη περιοχή του Αγίου Γεωργίου η αρχαιολογική έρευνα έφερε στο φως ένα χρυσό στεφάνι από φύλλα κισσού του 4ου αιώνα π.Χ.
Η πρωτοχριστιανική περίοδος στο Καστελλόριζο αντιπροσωπεύεται από το ψηφιδωτό δάπεδο μια βασιλικής που ήταν χτισμένη στον σημερινό ναό του Αγίου Γεωργίου Σαντραπέ στη περιοχή Χωράφια. Επίσης, έχει εντοπιστεί ψηφιδωτό δάπεδο στο καθολικό της ερημωμένης σήμερα μονής του Αγίου Γεωργίου του Βουνού. Οι ιστορικές πηγές σιωπούν για το νησί μέχρι τις αρχές του 14ου αιώνα όταν οι Ιππότες του Τάγματος του Αγίου Ιωάννη της Ιερουσαλήμ κατέλαβαν το νησί και έκτισαν το περιώνυμο Κόκκινο Κάστρο, από το οποίο σήμερα σώζεται ένας πύργος κι ένας προμαχώνας που στεγάζει το Μουσείο (Κονάκι). Τα αρχεία των Ιωαννιτών στη Μάλτα διέσωσαν το διάταγμα του Μέγα Μάγιστρου Jean de Lastic το 1440 που καλούσε τους Λίνδιους να προσφέρουν τις υπηρεσίες τους στα ιπποτικά καράβια, με σκοπό να αποτρέψουν επίθεση στο Καστελλόριζο από τους Μαμελούκους της Αιγύπτου.
Το νησί βρέθηκε, όπως και τα υπόλοιπα Δωδεκάνησα, στην εξουσία των Οθωμανών την εποχή του Σουλεϊμάν Β’ (1522). Η ιστορία έχει καταγράψει την πολιορκία του Κάστρου το 1778 από τους άνδρες του μικρού στόλου του Λάμπρου Κατσώνη που είχε καταπλεύσει στο Καστελλόριζο. Ύστερα από κανονιοβολισμούς και δύο ημερών σκληρό αγώνα, οι πολιορκούμενοι Τούρκοι παραδόθηκαν και ο Κατσώνης γκρέμισε τους προμαχώνες του Κάστρου. Κατά την διάρκεια των χρόνων της Επανάστασης του 1821 οι κάτοικοι μετέφεραν για λόγους ασφαλείας τα γυναικόπαιδα στην Κάρπαθο, την Κάσο και την Αμοργό.
Το 1836, με φιρμάνι του σουλτάνου Μαχμούτ Β’, παραχωρήθηκαν στο νησί προνόμια αυτοδιοίκησης, και κατ’ αποκοπή ετήσια φορολογία που ανερχόταν σε 480 χρυσές λίρες. Την εποχή εκείνη άκμασε οικονομικά και πληθυσμιακά εξαιτίας του αξιόλογου στόλου των κατοίκων που κτίζονταν στους ταρσανάδες στο Μανδράκι, και έκανε εμπόριο στα λιμάνια της Μαύρης Θάλασσας και της Δυτικής Ευρώπης. Το δεύτερο μισό του 19ου αιώνα μέχρι τις αρχές του 20ου υπήρξε εποχή κοινωνικής προόδου που οδήγησε στην επέκταση του οικισμού. Χαρακτηριστικά ήταν τα καπετανόσπιτα της γειτονιάς του Κάβου. Οι ντόπιοι την εποχή εκείνη διέθεταν κτηματική περιουσία και σπίτια στην απέναντι μικρασιατική παραλία.
Στο χρονολόγιο της ιστορίας του Καστελλόριζου έχει καταγραφεί η Επανάσταση των κατοίκων του την 1η Μαρτίου του 1913 εναντίον της τουρκικής διοίκησης του νησιού. Οι επαναστάτες εγκατέστησαν προσωρινή διοίκηση από ντόπιους πολιτοφύλακες που ενισχύθηκαν από 30 ένοπλους κρητικούς και από 23 σαμιώτες χωροφύλακες. Όμως κατά τη διάρκεια του Α’ Παγκοσμίου Πολέμου το νησί καταλήφθηκε στις 28 Δεκεμβρίου 1915 από τους Γάλλους. Τον Μάρτιο του 1921 έναντι μεγάλου τιμήματος το Καστελλόριζο πουλήθηκε στους Ιταλούς. Ένας καταστρεπτικός σεισμός στις 18 Μαρτίου 1926 προξένησε μεγάλες πληγές. Τον Φεβρουάριο του 1941 καταλήφθηκε για δυο ημέρες από τους βρετανούς κομάντος για να εξασφαλιστεί η αβλαβής διέλευση του Αγγλικού στόλου προς τον Πειραιά. Μετά τη συνθηκολόγηση των Ιταλών φασιστών το 1943, υποδεχόταν ανάμεσα στα συμμαχικά πλοία και το θωρηκτό «Παύλος Κουντουριώτης». Ακολούθησαν οι ανηλεείς γερμανικοί βομβαρδισμοί, που εκτός από τις μεγάλες καταστροφές, ανάγκασαν τους κατοίκους να εκπατρισθούν στις απέναντι ακτές και σε στρατόπεδο προσφύγων στη Κύπρο. Το κακό ολοκληρώθηκε με την μεγάλη πυρκαγιά του 1944. Μετά τον πόλεμο το ακριτικό νησί γνώρισε την αθρόα μετανάστευση των κατοίκων του, με χαρακτηριστική την κοινότητα των ξενιτεμένων Καστελλοριζιών στο Πέρθ της Αυστραλίας που αριθμεί περί τις 10.000 ανθρώπους.