Michailidis was born in Milikouri, Lefkosia province, Cyprus, on August 13, 1933. He studied Economics in Atlanta and returned to Cyprus where he worked in the island's tourist industry until the July 1974 Turkish invasion of Cyprus.
Michailidis entered politics in 1976 being elected to the House of Representatives under the banner of the Democratic Party of Cyprus. The following year, on August 3, President Makarios died and Spyros Kyprianou, as Speaker of the House, replaced him. Michailidis was in turn chosen to replace Kyprianou as Speaker of the House of Representatives, a post he served in until 1981.
In 1980, Michailidis left the Democratic Party, founding his own party - the New Democratic Alignment (NEDIPA) - which took 1.92% of the vote in the 1981 legislative elections but failed to elect any representatives.
In 1988, Michailidis joined the Democratic Rally Party (DISY) of Glafkos Clerides. When Clerides was elected President, Michailidis was appointed Foreign Minister serving at that post from February 28, 1993 until March 8, 1997. One of his main aims as Foreign Minister was the entry of Cyprus into the European Union which was achieved in 2004.