Skandalidis was born in Kardamaina, Kos, on November 11, 1953. He was elected to Parliament, under the banner of PASOK, in 1989 and was re-elected in the general elections 1990, 1993 and 2000. He is a member of the Standing Committee on Public Administration, Public Order and Justice.
Skandalidis has served as Minister for the Interior, Public Administration and Decentralisation from 24-10-2001 to 10-03-2004, Minister for the Aegean, 13-10-1993 to 08-07-1994; and Minister for the Interior, 08-07-1994 to 15-09-1995.
He was the Secretary of the PASOK Central Committee from 1995 until 22-10-2001. He is also the Chief editor of both the weekly and daily editions of "Exormisi", the PASOK newspaper (1985-1990).
On September 12, 2006, Skandalidis resigned his post as MP to concentrate on his candidacy for Mayor of Athens. On November 11, 2007, he challenged Giorgos Papandreou for the PASOK party leadership but lost.
Skandalidis is married with a son.