Colomba, a midfielder, started his playing career in Bologna, making his Serie A debut in 1973–74. He played for Bologna until 1983, except two loan spells at Serie B teams Modena and Sambenedettese, in 1975 and 1976 respectively. After having left Bologna, Colomba signed for Avellino, a minor Serie A team where he played until 1988, when Avellino relegated to Serie B, and became a favourite among the biancoverdi fans. He ended his career in 1990 with Modena.
After three years as youth coach for Modena and Spal, Colomba took his first head coaching job in 1993, at the helm of Olbia of Serie C2. After an impressive season with Novara one year later, in 1995 Colomba was called to coach Salernitana, where he narrowly missed immediate promotion to Serie A; he was fired one year later, because of poor results. In 1997, Colomba signed for Reggina of Serie B, where he obtained a seventh place. At the end of the season, he left Reggina for Serie A team Vicenza, where he however did not end the season, being fired after nineteen matchdays.
Colomba returned to Reggina in 1999, and stayed in Calabria for three seasons, with a relegation in 2001 (after having lost a play-off match to Verona) and a successive promotion in 2002. In the 2002–03 season, Colomba had a somehow turbulent Serie B experience at fallen giants Napoli, with a sacking and a successive recall, and a disappointing fifteenth place as a result. The next year saw Colomba making his third comeback at Reggina, but he is fired after the eleventh matchday and replaced by Giancarlo Camolese. The 2004–05 season started with Colomba at the helm of newly promoted Serie A side Livorno, but abruptly ended in January, when he was sacked and replaced by Roberto Donadoni. In October 2005, a Serie B team in danger of relegation, Avellino, called him to replace Francesco Oddo; however, Avellino finally lost its place to Serie B after two play-off matches lost to AlbinoLeffe.
On 19 July 2007 he was announced as head coach of Serie C1 club Verona. However, Verona had a very poor start in their Serie C1 2007–08 campaign, with no wins in the initial seven league matches, and a shock 1–2 defeat against Legnano led the club management to sack Colomba on 8 October 2007.
On December 2008 he was appointed as new head coach of Ascoli, becoming the third manager of the bianconeri in the Serie B 2008–09, and replacing Vincenzo Chiarenza. He guided Ascoli into a mid-table finish at the end of the season, but his contract was not extended and therefore left the club.
On 20 October 2009 Colomba was appointed new head coach of Bologna, taking over from Giuseppe Papadopulo. Notably, despite being born in Grosseto, Colomba grew up in Bologna and is a fan of the local club since childhood, and Bologna was also the club that gave him the chance to make his professional football debut. After taking the reins of the rossoblu club, he defined his appointment as head coach of Bologna as a dream coming true. He guided Bologna to keep their place in the Serie A in 2009–10, however his position was put under question after Sergio Porcedda took over the club. Originally confirmed at the helm of the club, he was ultimately dismissed on 29 August 2010, exactly one day before the first game of the season, allegedly due to disagreements with the board.
On 5 April 2011, Colomba was announced as the new head coach of Parma, replacing Pasquale Marino, and saved the club from relegation, being subsequently confirmed at the helm of the club also for the new season. On 9 January 2012, he was fired and replaced by Roberto Donadoni following Parma extended winless streak to six matches with a 5–0 loss to Inter.
Since 2014 he is the new coach of FC Pune City. He was send out by the refree during the second half of Pune's ISL match against Mumbai FC on December 3, 2014, for celebrating the team's two goals by running into the ground. He even ran to the goal keeper to celebrate. He had to watch the match from the VIP gallery for the rest of the match.