Es gibt keine eindeutigen Informationen über das ursprüngliche Baudatum der Festung.
Die Ritter des Johanniterordens, die von 1310 bis 1530 auf Rhodos ihren Sitz hatten, errichteten im 15. Jahrhundert mit Unterstützung der Genueser auf der Akropolis eine Kreuzritterburg, deren Ruinen heute noch weithin sichtbar sind. Teilweise ist noch gut zu erkennen, dass Reste einer weit älteren Bebauung mit einbezogen wurden.

In der Antike war der Name der Stadt Telmessos. Erstmals erwähnt wurde die Stadt unter dem Namen Telmessos im 5. Jahrhundert v. Chr. als Mitglied des attisch-delischen Seebundes. Ab dem 4. Jahrhundert v. Chr. stand sie unter lykischer Herrschaft. Telmessos bildete zusammen mit der etwa 18 Kilometer nördlich in den Bergen bei Üzümlü gelegenen heutigen Ruinenstadt Kadyanda die westliche Grenze des antiken Lykischen Städtebundes.

Ab dem 8. Jahrhundert, in byzantinischer Zeit, hieß sie Anastasiopolis nach dem Kaiser Anastasios II. Seit 1424 hieß die Stadt Megri bzw. griechisch Makri, was Ferne Stadt bedeutet. 1914 wurde sie zu Ehren des in jenem Jahr in der Nähe von Tiberias verunglückten ersten türkischen Militärpiloten Fethi Bey in Fethiye umbenannt.

Ein schweres Erdbeben der Stärke 7,1 zerstörte am 25. April 1957 den größten Teil der Stadt und der Kreuzritterburg, sechzehn Menschen wurden getötet und fast hundert verletzt. Bereits 1856 war die Stadt von einem starken Erdbeben betroffen. Im August 2004 und im Juni 2012 kam es ebenfalls zu beachtenswerten Beben mit einigen Verletzten und Schäden.