Fethiye is located on the Lycian and Carian border and was called Telmessos in antique times.
"Apollon the Lycian God, falls in love with the younger daughter of Agenor, the Phoenician King. In order to get closer to this timid young girl, he becomes a tiny, lovable dog. When the girl warms up to him, he makes his true identity known and they become lovers. After a while a son is born to them named Telmessos. This is where Fethiye's name is derived from antique times." In the absence of accurate information regarding teh exact date of its first foundation, based on the oldest written documents available, the town must have been in existence since the V. century B.C. and was called "Telebehi". The same name was also observed on silver coins remained from the same century.

Telmessos was for a long time an independent city separate from the Lycian Union.In 545 B.C., the Persian King Cyros's compatriot Harpagos conquered Telmessos together with some Carian cities. After that Telmessos, together with with the Lycians, became the first satrapy. The city joined the Attic-Delos Union towards the middle of the 5th century B.C., broke away from this union from time to time when participating various rebellions, but was involved with the union until the 4th century B.C.

In the 4th century B.C. Telmessos was adjoined to the Lycians by Pericles of Limyra who wished to establish the Union of Lycia. It is said that when Alexander the Great was on his Asian Campaign in 333 B.C., he stopped at Telmessos when the city opened up its doors without any apparent resistance. It is also said that this was by way of a successful stratagem.
"The armies of Alexander, during his Anatolian Campaign, stop at the port Telmessos. Nearchus requests Antiparides, the governor of the city at the time, to allow the entry of musicians and slaves into the city, and permission is granted. The slaves presumably carrying musical instruments are in fact armed warriors. During the night, when festivities are going on, the warriors arrange a surprise attack and conquer the acropolis."

After Alexander, the city was for a long time governed by the Ptolemy Dynasty. In 189 B.C. the Romans defeated Antiochus, conquered Anatolia and gave Telmessos to Bumenes, the King of Pergamum, under their command. After the fall of the Kingdom of Pergamum in 133 B.C. Telmessos became a member of the Lycian Federation and became one of the six major cities of this Federation.

According to one story, Telmessos was founded by a prophet and thus the city was bestowed with the power of prophecy. The best-known prophets of the archaic ages came originally and most respected. "One day an eagle landed on the yoke of the ox-cart belonging to Gordios, King of Phrygia, and the prophetess from Telmessos was asked to interpret this. The girl, not abusing her special powers, gave such a prophecy that Gordios was enchanted and immediately married her. A son was born to them, named as Midas, famous for his ears." Fortune-telling is still quite in fashion in Fethiye today.

During the 7th century particularly, Telmessos was weakened by the raids of the Arabs and lost its prominence. One source relates that in the year 1204 the Byzantian and the Turkish boundary went as far as Telmessos and the city was under Byzantian rule. In 1284 the city was conquered by Menteseogullari and became subject to Ottoman rule in 1424. Its name Makri during the Ottoman rule, meaning far-away land, was changed to Fethiye in 1914.