Η σημερινή ονομασία του νησιού τού αποδόθηκε στα τέλη του 14ου αι. από τους Ιωαννίτες Ιππότες, όταν αυτοί έκτισαν το κάστρο τους στην ίδια θέση που είχε κτίσει το αρχαίο οχυρό ο Ρόδιος Σωσικλής Νικαγόρας, επιστάτης της Μεγίστης. Κάτω από το κάστρο αναπτύχθηκε η πόλη. Πράγματι, όλα τα σπίτια του Καστελλόριζου έχουν κτιστεί στους πρόποδες του βουνού και αμφιθεατρικά γύρω από τη θάλασσα, ενώ ο παραδοσιακός οικισμός που συνιστούν (συνοικίες Πηγάδια, Χωράφια, Μανδράκι) έχει χαρακτηριστεί διατηρητέος, καθότι κατά παρόμοιο τρόπο με την περίπτωση της Σύμης, η ποικιλία της προέλευσης των οικοδομικών τους υλικών δημιουργούν εν τέλει μια ομοιομορφία απίστευτης αισθητικής. Σχετικά με το Μεσαιωνικό όνομα του νησιού υπάρχει η εξήγηση να προέκυψε από παραφθορά εκ του Castello Rosso, δηλ. το Κόκκινο Κάστρο, που ονομάστηκε έτσι επειδή οι βράχοι πάνω στους οποίους εκείνο υψώθηκε είναι κατακόκκινοι. Ωστόσο, σε μια προσπάθεια ερμηνείας του β’ συνθετικού (–ριζο), ο συγγραφέας και ερευνητής Ιωάννης Χατζηφώτης υποστηρίζει πως προέκυψε από το ριζοβούνι, δηλ. τους πρόποδες του βουνού, όπου και κτίστηκε το φρούριο (κάστελλος ή κάστελλον > λατ. castellum ).

Εκτός από τον οικισμό-στολίδι, κάτω από το κάστρο κοσμεί την ιστορία ένα θαλαμοειδές ταφικό μνημείο λαξευμένο στον βράχο, ο ναόσχημος Λυκιακός τάφος των τελών του 5ου αι. – αρχών του 4ου αι. π.Χ., της τεχνοτροπίας που συνήθιζαν στην Καρία και στη Λυκία. Στην ίδια εποχή (τέλη του 5ου αι. – αρχές του 4ου αι. π.Χ.) ανάγονται τα ερείπια τείχους ακρόπολης και τριών τουλάχιστων πύργων στο Παλαιόκαστρο, την τοποθεσία με τη μεγαλύτερη δυνατότητα εποπτείας και στρατηγικής σημασίας κατά την αρχαιότητα, της οποίας την αξιοποίηση αναδεικνύουν και οι Μεσαιωνικές επεμβάσεις που υπέστη. Δεν είναι σίγουρο πάντως αν οι Ιωαννίτες Ιππότες κατέλαβαν και το Παλαιόκαστρο ή αν το οχυρό τους ήταν μονάχα το Κόκκινο Κάστρο. Από αυτήν την περιοχή προέρχεται σημαντικός αριθμός αρχαίων επιγραφών, όπως και τμήμα Βυζαντινού ψηφιδωτού δαπέδου, μάλλον της Μονής της Παναγίας της Παλαιοκαστρίτισσας, ενώ από την παλαιοχριστιανική εποχή επιβιώνουν ερείπια τρίκλιτης βασιλικής κοντά στον ναό του Αγίου Γεωργίου Σαντραπέ.
Στην αρχαιότητα το νησί καταγράφεται ως Μεγίστη, όπως γράφει και ο Σκύλαξ, ο οποίος το τοποθετεί στη Λυκία μετά τα Πάταρα και τον Φέλλο. Ο Στράβων τοποθετεί τη Μεγίστη μετά την πόλη της Λυκίας Λίμυρα στη νότια ακτή της Μικράς Ασίας, στον ποταμό Λίμυρο, ενώ καταγράφει και μία πόλη της ονόματι Κισθήνη. Η πόλη αυτή όπως γράφει ο Smith (1857: 317) δεν υπήρχε την εποχή του Πλινίου, όπως και ο ίδιος άλλωστε γράφει, ο οποίος τοποθετεί το νησί στο Λύκιο εξίσου Πέλαγος. Αν και το νησί οφείλει το αρχαίο του όνομα στο γεγονός ότι είναι το μεγαλύτερο ανάμεσα στα πέριξ του νησιά, εκείνος που το αποδίδει σε μύθο είναι ο Λούκιος Κορνήλιος Αλέξανδρος ο Πολυίστωρ τον 1ο αι. π.Χ., ο οποίος χαρακτηρίζει τη Μεγίστη πόλη και νήσο της Λυκίας, ενώ καταθέτει πως ονομάστηκε από κάποιον Μεγιστέα, προφανώς τον πρώτο οικιστή της. Τον Πολυίστορα αντιγράφουν επακριβώς τόσο ο Ηρωδιανός στην Καθολική του προσωδία όσο και ο Στέφανος ο Βυζάντιος στα Εθνικά του, ενώ στα νησιά που βρίσκονται κοντά στη Λυκία συγκαταλέγει τη Μεγίστη νωρίτερα και ο Κλαύδιος Πτολεμαίος στο έργο του Γεωγραφική Ὑφήγησις.

Όπως συμβαίνει σε όλα τα νησιά που κατοικήθηκαν ήδη από τη Νεολιθική εποχή, πλήθος ευρημάτων κοσμούν και τη Μεγίστη, από προϊστορικά θραύσματα αγγείων και Κυκλώπεια Μυκηναϊκά τείχη, μέχρι και ευρήματα Κλασικής, Ελληνιστικής και Ρωμαϊκής περιόδου, όπως αυτό διαφαίνεται από τα ποικίλα εκθέματα μιας εκ των αιθουσών του Αρχαιολογικού Μουσείου Μεγίστης (επιγραφές, επιτύμβιες στήλες, ανάγλυφα Λυκιακού τύπου, βωμίσκοι, αγγεία και όστρακα, λυχνάρια, αμφορείς, κορμός μαρμάρινου αγάλματος Υγείας και τμήμα Ρωμαϊκής σαρκοφάγου). Ενδεικτικά, και όσον αφορά σε ευρήματα του 4ου αι. π.Χ., το Αρχαιολογικό Μουσείο Αθηνών φιλοξενεί τη χρυσή στέφανο που βρέθηκε σε σαρκοφάγο στην περιοχή του Αγίου Γεωργίου. Κατά τη Ρωμαϊκή περίοδο η Μεγίστη ανήκε στο Ροδιακό κράτος, γι’ αυτό και ο Σκύλαξ τη χαρακτηρίζει νήσο Ροδίων.

Σύμφωνα με τον Ρωμαίο ιστορικό Τίτο Λίβιο (1ος αι. π.Χ.-1ος αι. μ.Χ.), η Μεγίστη συνιστούσε ορμητήριο του Ρωμαϊκού στόλου κατά τον 3ο-2ο αι. π.Χ., ο οποίος γράφει (βλ. Ab Urbe Condita (37.45.2 ) πως επειδή ο Ρόδιος στρατηγός και ναύαρχος Πολυξενίδας που υπηρετούσε τον Σελευκίδη βασιλιά της Συρίας Αντίοχο Γ’ τον Μέγα (223-187 π.Χ.) φοβήθηκε τα Ρωμαϊκά πλοία που βρίσκονταν εκεί, κατευθύνθηκε πεζός μαζί με λίγους στη Συρία. Άλλωστε, από τον Λίβιο και πάλι (βλ. Ab Urbe Condita (37.22.5 ) μαθαίνουμε πως η χωρητικότητα του λιμανιού της Μεγίστης ήταν τέτοια ώστε να χωράει έναν στόλο, καθώς, όπως γράφει, από εκεί αναχώρησε τον 2ο αι. π.Χ. ο ναύαρχος Εύδαμος με έναν στόλο (uno agmine) για την πόλη Φασηλίδα της Λυκίας κοντά στη σημερινή Αττάλεια, όπου και του φάνηκε καλή ιδέα να περιμένει εκεί τον εχθρό, με σκοπό την παρεμπόδιση της έλευσης του Αννίβα στο Αιγαίο.

Στο νησί λατρεύονταν ο Δίας και ο Απόλλωνας Μεγιστεύς, ενώ από τον Αναστάσιο Βρόντη μαθαίνουμε πως τους δώδεκα γρανιτένιους κίονες του ναού του Απόλλωνα των Πατάρων της Λυκίας μετέφεραν σε σχεδίες κάτοικοι της Μεγίστης το 1830 στο νησί, προκειμένου με αυτούς να στηρίξουν τη στέγη του ναού των Αγίου Κωνσταντίνου και Ελένης (1835) στα Χωράφια, εξωραΐζοντάς τον. Ο Αλέξανδρος Πολυίστωρ όπως και ο Στέφανος καταγράφουν πως η πόλη πήρε το όνομά της από τον γιο του Απόλλωνα Πάταρο, ενώ στον ναό του Απόλλωνα των Πατάρων με το σπουδαίο μαντείο και μάλιστα δεύτερο αμέσως μετά από εκείνο των Δελφών, αναφέρεται ο Στράβων.

Σε σχέση με τη Βυζαντινή εθνολογία τόσο ο Επιφάνιος του 4ου αι. μ.Χ. όσο και ο συγγραφέας του Πασχάλιου χρονικού του 7ου αναφέρονται στον δεύτερο και τον τρίτο γιο του Νώε, τον Χαμ και τον Ιάφεθ αντίστοιχα, από τους οποίους κατάγονται σύμφωνα με τη Βίβλο όλοι οι σημερινοί λαοί της γης. Από τους απογόνους μάλιστα του Ιάφεθ κατάγονται οι Ινδοευρωπαίοι της Νοτιοανατολικής Ευρώπης. Και ενώ η Μεγίστη είναι ένα από τα 26 νησιά που ανήκουν κατά τον Επιφάνιο στον Χαμ και τους απογόνους του, όπως γράφει στο έργο του Ἀγκυρωτός, ένα από τα 26 και πάλι νησιά καταγράφεται στο Χρονικό του Πασχάλη ως επίκοινο των Χαμ και Ιάφεθ, ανήκει δηλ. από κοινού σε αυτούς και τους απογόνους τους.

Η Μεγίστη αποικίστηκε ή κατακτήθηκε από Δωριείς, όπως εξάλλου όλα τα Δωδεκάνησα, κι αυτό προκύπτει από το γεγονός πως όσες επιγραφές έχουν βρεθεί στο νησί είναι γραμμένες σε δωρική διάλεκτο. Ρωμαίοι, Βυζαντινοί, Ιωαννίτες Ιππότες, Αιγύπτιοι, Καταλανοί, Ισπανοί, Ενετοί, Ρώσοι, Οθωμανοί, Γάλλοι, Ιταλοί και Άγγλοι ακολουθούν, επαναλαμβάνοντας κατά κάποιον τρόπο την ιστορική μοίρα όλων των Δωδεκανήσων. Η διαφορά έγκειται όχι μόνο στη μη διαρκή Τουρκική κατοχή του νησιού αλλά και στο γεγονός ότι κατά τον Ιταλοτουρκικό πόλεμο αρχικά εξαιρέθηκε το Καστελλόριζο από την Ιταλική κυριαρχία (1912), στην οποία περιήλθε μόλις το 1921.

Στα μέσα του 20ου αι. παραμένει, ωστόσο, υπό συμμαχική στρατιωτική κατοχή, έως ότου μαζί με τα υπόλοιπα Δωδεκάνησα και μόλις δύο χρόνια έπειτα από τη λήξη του Β’ Παγκοσμίου πολέμου, στις 10/2/1947 με τη Συνθήκη των Παρισίων (Συνθήκη Ειρήνης με την Ιταλία) περιέρχεται πλέον στην Ελλάδα, συνιστώντας όχι μονάχα το ακρότατο νοτιοανατολικό της σημείο, αλλά κι εκείνο της Ευρώπης. Ελεύθερο πια, αλλά κατεστραμμένο σχεδόν ολοσχερώς από τους βομβαρδισμούς εκ μέρους των Γερμανών μετά τη βρετανική ανακατάληψή του το 1943, αυτό το στολίδι με τη μεγίστη χρονοαποθήκη κάλλους και τις πληγές ακόμη ανοικτές, χαρίζει στη θέαση ομορφιά και μόνο.