Millesi started his professional career at Sicily, firstly with Atletico Catania at Serie C1. He then played for Ragusa at Serie D. In 2000, he moved to Igea Virtus at Serie C2. At Igea Virtus, Millesi managed to score six goals in 70 matches over the two seasons. In 2003, he caught the eye of scouts from Avellino, the Serie B newcomer. He remained with his first club outside Sicily for three seasons, scoring 16 goals in 88 matches He also played 6 playoffs and scored twice. In 2006, he transferred to Calcio Catania, who were just promoted to Serie A for the 2006–07 season. He played only 9 league matches in the first season. After played only once in the start of the second season, he was loaned to then Serie B club, Spezia. After failed to sell the player in 2008–09 season. At the mid of 2009 summer transfer windows, Catania announced the contract terminations under mutual consent for both Millesi and Babu. On 31 August 2009, he signed a 1+1 contract with Salernitana of Serie B. On 1 February 2010, he moved to Foggia. On 15 November, he returned to Avellino, where he soon became the club's captain, and was one of the team's leading figures in the club's promotions from Lega Pro Seconda Divisione to Serie B, also helping the side narrowly miss out on the 2013–14 Serie B promotion play-offs; he left Avellino at the end of the season. On 9 September 2014, he signed with Arezzo. On 21 January 2015, he moved to Ischia Isolaverde. At the end of the season, he was once again a free agent, and he signed with Acireale on 30 October 2015, ahead of the 2015–16 Eccellenza Sicilia season. For the 2016–17 season, he was signed by Eccellenza Sicilia Group B side A.S.D. Calcio Biancavilla, at the request of the club's president Giuseppe Furnari.
Match-fixing
On 23 May 2016, Millesi, along with fellow midfielder Luca Pini and defender Armando Izzo, was put under investigation by the anti-mafia police department in Naples after being accused of being directly involved with a camorra clan based in Secondigliano in altering the results of the Serie B matches Modena–Avellino from 17 March 2014, and Avellino–Reggina from 25 May 2014. On 3 March 2017, the Italian football federation's prosecutor asked for all three players to be banned from football for six years, also requesting that collateral estoppel be applied, and demanded that they should each receive a €20,000 fine. On 12 April, both Millesi and Pini received five-year suspensions and €50,000 fines.
