Messina had two different stints as the head coach at the Italian League team, Virtus Bologna. In the 1989–90 season, he won the Italian Cup and also the second-tier level European-wide league, the FIBA Cup Winners' Cup, against Real Madrid, in Florence. He also won the Italian League national championship in 1993. During his second stint at Virtus, he coached the team to win the first-tier level European-wide EuroLeague championship, in both 1997–98 and 2000–01. He also added two Italian League championships to his trophy case in 1998 and 2001, as well as three Italian Cup titles in 1999, 2001, and 2002.
Messina then served as the head coach of the Italian League club Benetton Treviso, where he succeeded Mike D'Antoni as head coach, in 2002. He stayed there for 3 seasons. With Treviso, he won the Italian League championship in 2003, and also the Italian Cup title thrice, adding them to a total streak of 5 consecutive titles, with two different clubs.
Messina then joined the Russian club CSKA Moscow in 2005, and led the team to the EuroLeague's 2005–06 title, and the coveted Triple Crown, in his first season there. On 4 May 2008, CSKA won the EuroLeague championship again under Messina - the club gained its sixth EuroLeague title by downing Maccabi Tel Aviv at the 2007–08 Madrid edition of the EuroLeague Final Four. He resigned from CSKA immediately after leading them to a Russian Championship and the EuroLeague Final, during the 2008–09 season. He was offered a position as the technical director at CSKA, but at the time of his resignation, he had not decided whether or not he wanted to stay with the club.
Real Madrid
Messina was announced as the new head coach of the Spanish League club Real Madrid, on 18 June 2009, and signed his contract with the club the following day. After Real Madrid had several poor performances, Messina resigned from the club's head coach position, in March 2011.
Messina was frequently the subject of speculation linking him with vacant coaching jobs in the NBA. For example, he was one of the many coaches in the discussion for the Sacramento Kings head coaching role, and it was also rumored that he would join the Toronto Raptors and San Antonio Spurs coaching staffs. Messina eventually agreed to join the Los Angeles Lakers, as part of head coach Mike Brown's coaching staff, as a full-time consultant to the head coach, for the 2011–12 season.
Return to CSKA Moscow
In June 2012, Messina decided to leave his job as a consultant for the Los Angeles Lakers, and he returned to CSKA Moscow, to become the team's head coach. In June 2014, he parted ways with CSKA Moscow.
San Antonio Spurs
On 15 July 2014, Messina was hired by the San Antonio Spurs, as an assistant coach. On 16 October 2014, Messina would coach the Spurs in a 121–90 preseason win against the Phoenix Suns, due to Gregg Popovich being unable to travel with the team at the time. Messina would later take on the role of the World Team's head coach in the 2016NBA Rising Stars Challenge. On 7–8 March 2016, Messina again served as head coach of the Spurs, for two games, due to Gregg Popovich leaving the team for a family emergency. On 19 April 2018, Messina temporarily took over head coaching duties of the team in their playoff series versus the Golden State Warriors, due to Popovich having left the team in light of his wife's death the previous night.
Olimpia Milano
On 11 June 2019, Messina signed a three-year contract, and agreed to become the new head coach and President of Basketball Operations of the Italian club Olimpia Milano.
