Malezas in 2013
|Full name||Stylianos Malezas|
|Date of birth||11 March 1985|
|Place of birth||Katerini, Greece|
|Height||1.93 m (6 ft 4 in)|
|Playing position||Centre back|
|2004–2005||→ Irodotos (loan)||30||(1)|
|* Senior club appearances and goals counted for the domestic league only and correct as of 21:30, 4 April 2018 (UTC)|
He started his career at AEP Katerini and moved to PAOK in 2003, thus signing his first professional contract. He plays as a centre back, having formerly played as a defensive midfielder. In the 2008–09 season, he gained his place in the starting eleven, making some regular first-team appearances. On 6 February 2009, he signed a new contract with PAOK, which would keep him at the club until 2013. During all these years he played 164 games with PAOK in all competitions.
Defender Malezas of Greek club PAOK FC, is making the move to Germany for a reported fee of €577,000 (£450,000), with the money being paid in installments over the next 12 months. Malezas was on Monday undergoing a medical and Fortuna Düsseldorf, who last season won promotion via the play-offs, are then expected to officially announce a three-year contract. General manager Wolf Werner told Express newspaper: "We are about to sign Stelios Malezas from PAOK of Greece." 
In December 2013, Malezas was informed that is already named for returning to his former club PAOK and in an interview held from PAOK24 he said: "As a mark of respect for the club, it must be clear that the given time there has been no communication with people of PAOK nor the possibility of my return to it. I have a contract with Fortuna until summer. I do not know what will happen in January and after that I have the right to negotiate, but as we speak there is absolutely not any communication with PAOK." Otherwise Malezas would not say no to the possibility of a return to PAOK, but this time there is nothing to confirm that he wants to leave Germany.
The German dream seems to take a fee for Stelios Malezas, who the summer of 2014 will be past for the roster of Fortuna Düsseldorf. He failed to prove his worth to the people of the German club and specifically, the former PAOK defender has only made 10 appearances after half of the season passed. The coach of Fortuna, Lorenz-Günther Köstner believes that the former Thessalonian player can not cope with the demands of the team, so it can be assumed that is almost in exit. Eventually on May 23, 2014 after two years with the club was informed that there was not in the staff's plan for next season. Malezas stated that " Everybody does not like goodbyes, but I must do it. I have no choice".
Return to PAOK
On 10 August 2015, Malezas joined for a second spell PAOK, signing a two years' contract for an undisclosed fee. His first year after his return, was disappointed but gradually became a member of the starting XI especially under Vladimir Ivić coaching. As a result of his performances, the administration of PAOK has decided to extend the contract of the experienced central defender. He is expected to sign a new two-season contract, as he was recently informed by athletic director of the club, Lubos Michel.
On March 1, 2017, PAOK made public his agreement for a one (plus one) year contract with the international defender, and Malezas was extremely happy as he signed with the team that showed him, in whose ranks he spent less than ten years. On 27 June 2017, the probability to continue his career in the club will be changed as there is interest from Russian Premier League club FC Anzhi Makhachkala. On 16 December 2017, PAOK achieved its second consecutive away victory at the 2017-18 season, against struggling Platanias at Perivolia Municipal Stadium, as the experienced central defender and captain of the Greek Cup winners, bagged the only goal of this clash, with a close-range effort at 56'. It was his first goal with the club since his return from summer of 2015. On 6 June 2018, experienced central defender and captain of PAOK, Stelios Malezas, will renew his contract with the Greek Cup winners until the end of 2018-19 season. The owner and president of historic Thessaloniki club, Ivan Savvidis, had publicly promised after victory over AEK at 2017-18 Greek Cup final that the contract of 33-year-old international defender will be extended, something which was officially announced.
On 28 February 2010, he was called up to represent Greece in a friendly against Senegal. On 1 June it was announced that he would be in the 23-man squad for the 2010 FIFA World Cup. He was also to the 23-man squad for the UEFA Euro 2012.
- As of 12 May 2018
|2004–05||P.A.S.A. Irodotos F.C.||Gamma Ethniki||30||1||4||0||0||0||34||1|
- "Stats Centre: Stilianos Malezas Facts". Guardian.co.uk. Retrieved 8 April 2009.
- "Malezas moving to Fortuna". Retrieved 30 July 2012.
- "Δεν έχω πρόταση από ΠΑΟΚ". Retrieved 5 December 2013.
- "Ανεπιθύμητοι οι Μαλεζάς και Γιαννιώτας στη Φορτούνα Ντίσελντορφ". exedra.gr. Retrieved 20 March 2014.
- "Τέλος ο Μαλεζάς από τη Φορτούνα Ντίσελντορφ". 23 May 2014.
- "Μαλεζας: Έκλεισε ο κυκλος μου στην Φορτουνα". 7 June 2014.
- Μαλεζάς διετίας στον Παναιτωλικό (in Greek). sport24.gr FC. 11 July 2014. Retrieved 11 July 2014.
- Stelios Malezas returns to PAOK;10 August 2015
- Stelios Ανζί καλεί Μαλεζά;27 June 2017
- Μίλησε πάλι η ελληνική ψυχή, Πλατανιάς - ΠΑΟΚ 0-1 με Μαλεζά;16 December 2017
- ΠΑΟΚ: Το είπε και το έκανε ο Ιβάν Σαββίδης: Μένει Τούμπα ο Μαλέζας!;6 June 2018
- Stelios Malezas