Lemonis was born on January 13, 1960. He played for local club Attikos before being acquired by Olympiakos. He played for the red-and-whites from 1979 until 1987. After that, he also played for Levadiakos (1988 - 1991).
During his playing career Lemonis was capped twice by the Greek National Football Team.
Following his playing career, Lemonis studied coaching in England and, in 1996, became head coach at Asteras Zografos. In 2000, he returned to Olympiakos as assistant coach and, after the dismissal of Yiannis Mantzourakis, as head coach. Lemonis had domestic success at Olympiakos but internationally fell short of the fans' expectations and was dismissed in October of 2002. He has since coached APOEL in Cyprus (2003), Kallithea FC (2005) and Levadiakos upon their return to the Alpha Ethniki for the 2006 season.
In September 2006, Lemonis once again replaced Yiannis Mantzourakis, this time as coach of SKODA Xanthi. He resigned in December 2006 and, later that month, replaced Trond Sollied at the helm of Olympiakos once again.