Ada, tarihinin ilk dönemlerinde Dorlar tarafından kolonize edilmiş ve Megisti adını almıştır. Aya-Nikolon (eski kale) kalesinde bulunmuş olan yazıtlar adanın Helenistik Dönem boyunca, Rodos tarafından yönetilmiştir doğrular. Rodoslular adaya bir genel müfettiş gönderirmiş.
Bizans imparatorluğu döneminde, Kastelorizo-Megiste başkenti Rodos olan “ Adalar Eyaleti”’nin bir parçası idi. Bu eyalet temel olarak denizciliğe bağlıydı. Ortaçağlar boyunca Bizans ve Osmanlılar adayı ele geçirmek için mücadele ettiler.
1306’da Folques de Villaret liderliğindeki Kudüslü St. John şövalyeleri adanın kontrolünü ele geçirdiler. O dönemde Kıbrıs’tan Rodos’a gitmekteydiler. Üç yıl sonra Rodos’u fethedip Haçlı Devletinin merkezi yaptılar. Şövalyeler kaleyi restore edip sadık olmayan şövalyeler için hapishane olarak kullandılar. 1440’ ta ada Mısır sultanı Cemalettin tarafından işgal edilip kale yıkıldı. 10 yıl sonra ada Napoli kralı Aragonlu 5. Alfons tarafından fethedildi. Kale tekrar yapılıp adaya bir vali gönderildi. Napoli Krallığı, adayı 1512 yılına kadar elinde tuttu ve 1512’de ise ada Kanuni Süleyman tarafından fethedildi.
22 Eylül 1659’ da, Girit Savaşı sırasında ada Venedik tarafından alındı ve kale tekrar yıkıldı ancak Osmanlılar kısa bir süre sonra adayı geri aldılar.
1828-1833 yılları arasında Kastelorizo (Kızılkale) Yunan ayaklanmasına katıldı ancak Yunan Bağımsızlık Savaşının bitiminden sonra tekrar Osmanlı İmparatorluğu hakimiyetine geçti.
1912’de, Osmanlı ve İtalya arasında yapılan Libya Savaşı sırasında ada halkı Rodos’taki İtalyan işgal kuvvetleri komutanı General Ameglio’dan İtalya’ya bağlanmayı istediler. Bu teklif reddedilince 14 Mart 1913’te Osmanlı garnizonunu ele geçirip geçici bir hükümet ilan ettiler. Aynı yılın Ağustos ayına kadar Yunan hükümeti Samos adasından jandarma destekli bir müfettiş gönderdi. Bunlar 20 Ekim 1915’te ada halkı tarafından kovuldular. 28 Aralık 1915’ te “ Janne d’Ark” adlı kruvazörle gelen Fransız askeri birlikleri adaya çıktılar ve aynı anda adaya çıkmaya çalışan Yunan Evzones’in çıkışını engellediler. Türk sahil bataryaları Fransız işgaline, adayı top atışına tutarak cevap verdiler ve 1917’ de HMS Ben-my-Chree gemisini batırmayı başardılar. Sevr Antlaşması şartlarına göre ada İtalya’ya teslim edildi ve İtalyan donanması, adayı Fransız donanmasından 1 Mart 1921’de devraldı. Kastelorizo- İtalyanca Kızılkale- böylelikle Ege İtalyan adalarına katıldı.
1932’ de İtalya ve Türkiye arasındaki deniz sınırlarını belirleyen anlaşmayla –Rho ve Strongili adaları hariç- Kastelorizo çevresindeki küçük adaların hepsi Türkiye’ye teslim edildi.
1930 ‘lu yıllar boyunca Roma’dan Beyrut’a giden İtalyan ve Fransız uçaklarının durak yeri oldu.
İkinci dünya Savaşı sırasında 25 Şubat 1941’de İngiliz komandoları adayı işgal ettiler ancak bir süre sonra Rodos’tan gelen İtalyan birlikleri adayı geri aldı. İtalya müttefiklere teslim olduğunda ( 8 Eylül 1943) Eylül ayı içerisinde ada İngiliz komandolar tarafından kısa süreliğine tekrar işgal edildi fakat 1944’te Alman kuvvetleri adayı kontrolüne geçirdi. İngilizlerin ayrılması sırasında bir yakıt deposu alev aldı ve yangın bitişikteki dökme cephaneye sıçradı. Patlama, adadaki evlerin yarısının yıkılmasına neden oldu.
Kastelorizo, 1947 Paris Anlaşması şartlarına göre Yunanistan’a devredildi. Mayıs 1947’ de hala Britanya yönetimindeydi ancak 15 Eylül 1947’de fiili olarak Yunanistan yönetimine geçti. Ada, resmi olarak 7 Mart 1948’de On iki Adalarla birlikte Yunanistan Hükümetine bağlandı.
Ada, daha çok son yıllarda gözlerden uzak On iki Adalar’a giden turistler tarafından ve 1992’de En iyi Yabancı dilde Film Oskarı alan Gabriele Salvatores ( 1991) yapımı “ Akdeniz” adlı filmden dolayı ziyaret ediliyor.
Kastelorizo 29 Mart 2006 güneş tutulmasının tam olarak görüldüğü tek Avrupa Birliği toprağı idi.
