Colantuono, a centre back, started his playing career for Serie D side Velletri in 1981. In 1983 he moved to Ternana of Serie C1, then Arezzo of Serie B, and finally made his Serie A debut for Pisa. He played Serie A until 1990 for several teams. In 1991 he accepted to play in the national futsal league for BNL Roma, winning a scudetto. Following this experience, Colantuono played mostly at lower levels, especially Serie C2 and Serie D, and even Eccellenza for Sambenedettese in 1994–1995. After a long list of experiences in different Italian regions, Colantuono returned to play for Sambenedettese in November 2000, leading his team to an immediate promotion to Serie C2.
The 2001–2002 Serie C2 season for Sambenedettese was going to be very hard, with two coaches fired throughout the season. After the sack of third coach Enrico Nicolini, Colantuono, a player for the team, was appointed to manage Sambenedettese together with Gabriele Matricciani for the last nine matches. Surprisingly, Colantuono managed to win all these nine matches, leading his team to a fifth place, qualifying and successively even winning the promotion playoffs.
Colantuono's Serie C1 coaching debut, in 2002–2003, ended in another fifth place, securing a place in the promotion playoff, then lost to Pescara. In the meanwhile, Luciano Gaucci, owner of Sambenedettese, Serie B team Catania and Serie A team Perugia at the time, appointed Colantuono at the helm of the Sicilian side. Colantuono, again supported by Matricciani because of his lack of a regular coaching license, led Catania to a fairly good season in ninth place. In 2004–2005, after Catania was sold by the Gaucci family, Colantuono, finally authorized to act as first team coach, signed for Perugia, just relegated to Serie B. He led the team to a spot in the promotion playoff, then lost to Torino. After the cancellation of Perugia, in 2005–2006 Colantuono accepted the offer of Atalanta, leading the nerazzurri to a clear Serie B win. In the season 2006–2007 he led Atalanta to an impressive seventh place in the Serie A table.
On 31 May 2007, he was announced as new Palermo head coach to replace Francesco Guidolin. However after a number of unimpressive performances ended by a crushing 5–0 loss to Juventus persuaded club chairman Maurizio Zamparini to sack him on 26 November 2007. He was once again recalled on 24 March 2008 to replace Guidolin as head coach of Palermo. However, Colantuono was sacked again after just one game of the 2008–2009 season, and was replaced by Davide Ballardini on 4 September.
On 15 June 2009 he was appointed as new head coach of Torino, replacing Giancarlo Camolese. He will guide the granata through their 2009–10 Serie B campaign, with the aim to promptly lead the historical Turin club back into the top flight. He was however fired on 29 November due to poor results and replaced by Mario Beretta. On 10 January 2010 he was then reappointed as head coach to replace Beretta himself. He announced his resignation after losing the promotion playoff finals to Brescia, contemporaneously confirming he was in talks for the vacant coaching post at his previous club Atalanta. Colantuono's comeback at Atalanta was officially announced the next day. Under his tenure, Atalanta promptly won promotion back to the top flight in his first season in charge.